LeetCode 303. Range Sum Query - Immutable (C++)

题目:

Given an integer array nums, find the sum of the elements between indices iand 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:

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

分析:

题目的意思很简单,给定一个数组,使用sumRange(i,j)函数来计算两个索引之间元素的和。

最简单的方法便是根据给的i,j直接求和。不过在note中我们看到会多次调用sumRange这个函数,如果每次调用都重新求这样时间复杂度会很高。

现在我们开辟一个新的sums数组,大小和nums一样大。其中sums[ i ]表示nums[ i ]之前所有元素的和(包括nums[ i ]这个元素)。

根据样例nums = [-2,0,3,-5,2,-1],我们可以求出sums = [-2,-2,1,-4,-2,-3]。

sums[1] = nums[0] + nums [1] = -2 + 0 = -2

sums[3] = nums[0] + nums [1] + nums[2] + nums [3] = -2 + 0 + 3 + -5 = -4

我们来看当调用sumRange(i,j)时实际上就是要求nums[ i ] + nums[ i+1 ] + ... + nums[ j -1 ] + nums[ j ]的和。

而我们刚才求的sums数组其中:

sums[ i-1 ] = nums[0] + nums[1] + ... + nums[ i-1 ]

sums[ j ] = nums[0] + nums[1] + ... + nums[ j ]

因为i <= j 所以有sums[ j ] - sums[ i-1 ] = nums[ i ] + nums[ i+1 ] + ... + nums[ j -1 ] + nums[ j ]

这样在开始求一次sums数组,便可以在多次调用sumRange事不在重复计算了。可以直接返回sums[ j ] - sums[ i-1 ] 。

注意当i = 0时要做特殊的处理,sumRange(0,j) = sum[ j ],也就是直接返回 sum[ j ]就可以了因为它本身就是nums[ j ]之前所有元素的和。

程序:

/*class NumArray {
public:
NumArray(vector<int> nums) {
myNums.swap(nums);
} int sumRange(int i, int j) {
int sum = 0;
for(int q = i; q <= j; ++q){
sum += myNums[q];
}
return sum;
}
private:
vector<int> myNums;
};*/
class NumArray {
public:
NumArray(vector<int> nums) {
for(auto i:nums){
if(sums.empty())
sums.push_back(i);
else
sums.push_back(sums.back()+i);
}
} int sumRange(int i, int j) {
if(i == )
return sums[j];
else
return sums[j]-sums[i-];
}
private:
vector<int> sums;
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
上一篇:20165223 week2学习查漏补缺


下一篇:jvascript 顺序查找和二分查找法