題目：
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.
解析：
這一題是求指定區(qū)間數(shù)組元素的和孕蝉。并且要求不能改變?cè)瓟?shù)組溪北。這個(gè)方法會(huì)經(jīng)常被調(diào)用寥假。
由于經(jīng)常被調(diào)用盲泛，如果按常規(guī)方法妄壶，開銷會(huì)比較大摔握，每次都要遍歷并求和。已知數(shù)組不會(huì)改變丁寄，我們可以考慮能不能先計(jì)算一部分氨淌，節(jié)約后面調(diào)用的開銷。
重新定義一個(gè)數(shù)組伊磺，這個(gè)數(shù)組保存從第一個(gè)元素到當(dāng)前元素的累計(jì)值∈⒄現(xiàn)在想想，再求一個(gè)區(qū)間屑埋，只需要求兩個(gè)值的差即可豪筝。
原數(shù)組：[1，2雀彼，1壤蚜，9，5]
保存的數(shù)組：[0徊哑，1袜刷，3，4莺丑，13著蟹，18]
sumRange(2墩蔓，4) = 18 - 3 = 15
Q:為什么第一個(gè)元素要置0?
有時(shí)候在思考一個(gè)問題時(shí)，可以反著思考萧豆，比如：如果不置0會(huì)怎么樣奸披？
那么就需要判斷邊界條件，首先是代碼不夠清晰涮雷，分支多阵面；其次，性能也有影響洪鸭。而加一個(gè)0可以將問題表現(xiàn)統(tǒng)一样刷。 這里有興趣的可以去看看linus 用雙重指針操作鏈表的例子。鏈接
我覺得這題體現(xiàn)出把計(jì)算提前的思想览爵，比如模板元編程置鼻，可以在編譯期間計(jì)算出結(jié)果，而不用在運(yùn)行時(shí)計(jì)算蜓竹，運(yùn)行次數(shù)越多箕母，越體現(xiàn)優(yōu)勢(shì)。
答案：
class NumArray {
private:
vector<int> sumArray = {0};
public:
NumArray(vector<int> nums) {
int sum = 0;
for (int n : nums) {
sum += n;
sumArray.push_back(sum);
}
}
int sumRange(int i, int j) {
return sumArray[j + 1] - sumArray[i];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
