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) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
如果不考虑Note的话，这个题没什么可说的，可是如果这个方法会被调用很多次，且数组是不变的，那我们的想法就是，在初始化的时候来做一些事情，让每次调用都可以直接取到结果。
首先想到的是使用HashTable，但是这样要保存几乎n方个数据。
我们新建一个数组sum，让每第i个值是num数组中前i-1个值的和，比如sum[0]=0,sum[1]是前一个数的值，sum[2]是前两个数的值。这样我们在请求第i到第j个元素的和的时候，就可以用前j个元素的和减去前i-1个元素的和，也就是sum[j+1]-sum[i]。
比如：
array=[4,3,1,5,6];
sum =[0,4,7,8,13,19];
i=2;j=4;1+5+6 = 12
sum[4+1]-sum[2]=19-7=12;
/**
* @constructor
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.sum = [0];
var num = nums.length;
for (var i = 0; i < num;i++) {
this.sum[i+1]=this.sum[i]+nums[i];
}
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
return this.sum[j+1]-this.sum[i];
};
