303. Range Sum Query - Immutable
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) -> -3Note:
You may assume that the array does not change.
There are many calls to sumRange function.
题目大意：求数组一个连续子集的和。
思路：
1.可以直接找到数组子集的起始位置，连续相加到终止位置，
就可以得到答案。这样的话，没计算一次都要连续相加，比较麻烦。所以想到下面的思路。
2.用一个数组来存放当前元素的之前元素的和。
例如：
vector<int> source,源数组
vector<int> preITotal,用来存放source前i个元素的和，包括第i个元素。
以后每次计算范围源数组[i,j]范围子集的和，preITotal[j] - preITotal[i-1].计算即可。
代码如下：
class NumArray {
private:
vector<int> preITotal;//存放前i个元素的和
public:
NumArray(vector<int> &nums) {
if(nums.empty())
return;
preITotal.push_back(nums[0]);
for(int i = 1; i < nums.size(); ++i)
preITotal.push_back(preITotal[i-1] + nums[i]);
}
int sumRange(int i, int j) {
if(0 == i)
return preITotal[j];
return preITotal[j] - preITotal[i - 1];
}
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);题目标注为动态规划，开始怎么也想不出哪里用到动态规划的思想了。当把当前的结果记录下来，以后使用这一点，和动态规划挂钩了。
2016-08-31 22:42:39
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
