303. Range Sum Query - Immutable

Given an integer arraynums, find the sum of the elements between indicesiandj(i≤j), inclusive.

Example:

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


Note:

You may assume that the array does not change.

There are many calls tosumRangefunction.

题目大意：求数组一个连续子集的和。

思路：

1.可以直接找到数组子集的起始位置，连续相加到终止位置，

就可以得到答案。这样的话，没计算一次都要连续相加，比较麻烦。所以想到下面的思路。

2.用一个数组来存放当前元素的之前元素的和。

例如：

vector<int> source,源数组

vector<int>preITotal,用来存放source前i个元素的和，包括第i个元素。

以后每次计算范围源数组[i,j]范围子集的和，preITotal[j] -preITotal[i-1].计算即可。



代码如下：

classNumArray{private:vector<int>preITotal;//存放前i个元素的和public:NumArray(vector<int>&nums){if(nums.empty())return;preITotal.push_back(nums[0]);for(inti=1;i<nums.size();++i)preITotal.push_back(preITotal[i-1]+nums[i]);}intsumRange(inti,intj){if(0==i)returnpreITotal[j];returnpreITotal[j]-preITotal[i-1];}};//YourNumArrayobjectwillbeinstantiatedandcalledassuch://NumArraynumArray(nums);//numArray.sumRange(0,1);//numArray.sumRange(1,2);

总结：

题目标注为动态规划，开始怎么也想不出哪里用到动态规划的思想了。当把当前的结果记录下来，以后使用这一点，和动态规划挂钩了。


2016-08-31 22:42:39