Lipsky

LeetCode 303. Range Sum Query - Immutable

字数统计: 272阅读时长: 1 min
2020/02/26 Share

303. Range Sum Query - Immutable#

303. Range Sum Query - Immutable

Description#

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

Example:#

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class NumArray {
int[] sum;
public NumArray(int[] nums) {
sum = new int[nums.length+1];
for (int i = 0; i < nums.length; i++){
sum[i+1] = sum[i] + nums[i]; //S(n) = S(n-1) + f(n);
}
}

public int sumRange(int i, int j) {
return sum[j+1] - sum[i]; //S(n+2) - S(n) = f(n+1) + f(n+2);
}
}

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
* C++
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(i,j);
*/
class NumArray {
public:
NumArray(vector<int>& nums) {
int n = nums.size();
if (n==0) return;
sum_ = vector<int> (n, 0);
sum_[0] = nums[0];
for (int i=1;i<nums.size();i++){
sum_[i] = sum_[i-1] + nums[i];
}
}

int sumRange(int i, int j) {
if(i==0) return sum_[j];
return sum_[j] - sum_[i-1];
}
private:
vector<int> sum_;
};

image-20200226224942382

Time Complexity: Query$O(1)$ Pre-calculate $O(n)$

Space Complexity: $O(n)$

CATALOG
  1. 1. 303. Range Sum Query - Immutable#
  2. 2. Description#
  3. 3. Example:#