Leetcode No.303(Range Sum Query — Immutable) 心得

ChingYuanYang
Aug 28, 2017 · 2 min read

題目:
Given an integer array nums, find the sum of the elements between indices i and j (ij), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

想法: 這題的關鍵在於同一個陣列會呼叫很多次,所以很明顯要先處理好數據,我靈機一動就想到先把 [0, n] 這個範圍的 Sum 先加好存到 arraySum,之後兩兩相減就是這兩個之間的和。這題也複習 vector 和 class 用法,以及要注意對於 input vector size = 0 的處理,還有 arraySum 兩兩 index (i, j) 相減其實是 [i+1, j] 的加總。
Note: 題目commets得地方有錯,因為是 new,所以應該要
* int param_1 = obj.sumRange(i,j);

class NumArray {
public:
NumArray(vector<int> nums) {
int size = nums.size();
if (size == 0) return;
arraySum.push_back(nums[0]);
for (int index = 1; index < size; index++) {
arraySum.push_back(arraySum[index — 1] + nums[index]);
}
}

int sumRange(int i, int j) {
if (arraySum .size() == 0) return 0;
if (i == 0) return arraySum[j];
else return arraySum[j] — arraySum[i-1];
}
private:
vector<int> arraySum;
};

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/

網路上的做法:
有一個做法是用 hash map 把所有 [i,j]範圍內的值先算法,這樣可以少了減法時間和一個 access time,只是在建構 map會花比較多時間。

Complexity analysis

  • Time complexity : O(1) time per query, O(n²) time pre-computation. The pre-computation done in the constructor takes O(n²)time. Each sumRangequery’s time complexity is O(1)as the hash table’s look up operation is constant time.
  • Space complexity : O(n²). The extra space required is O(n²) as there are n candidates for both i and j.
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

public NumArray(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
map.put(Pair.create(i, j), sum);
}
}
}

public int sumRange(int i, int j) {
return map.get(Pair.create(i, j));
}
)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade