区域和检索-数据不可变

给定一个整数数组  nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

实现思路

下标	0	1	2	3	4	5	6
nums	-2	0	3	-5	2	-1	--
preCount	0	-2	-2	1	-4	-2	-3

使用preCount存储前面的值，sumRange函数仅需要做一次减法运算，避免了每次进行 for 循环调用，最坏时间复杂度为常数 O(1)

var NumArray = function(nums) {
    this.preCount = [0]
    for(let [key, value] of nums.entries()){
        this.preCount[key+1] = this.preCount[key] + value 
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    return this.preCount[right+1] - this.preCount[left]
};

上面的计算过程也可以用reduce实现，基本思路是一样的。

var NumArray = function(nums) {
    this.preCount = [0]
    nums.reduce((pre, cur) => {
        this.preCount.push(pre + cur)
        return pre + cur
    }, 0)
};