不可变数组求和

标注：

本文有参考 别人家的面试题：不可变数组快速范围求和

来源：十年踪迹的博客

本文并非抄袭月影的文章，而是加入了自己的认识。

解题思路:

最笨的实现方式就是遍历区间求和。但是题目要求：

sumRange 可能会被使用很多次，求不同范围的值

既然多次使用，为避免重复计算，应该容易想到缓存计算结果。

如何缓存

虽然想到了缓存方案，但具体如何缓存呢，缓存的数据结构应该是什么样子？怎么应用缓存的结果？

思考过程：

区间的取值：
i 的范围 0 - n，j 的范围 0 - n。 即 0 ~ i ~ j ~ n;

倒推法：我们要的结果是区间范围 [i,j] 之和，按照直观的想法，我们很容易想到遍历 [i,j] 然后累加计算，然后顺着这个思路，如果采用遍历累加计算方案，我们能缓存下来什么？缓存每次的计算结果？ 这样就是查表法了。

可是仔细想一想，这个排列组合有多少种？参考下 i,j 的取值范围，n*n，也就是至少要计算 n*n 次才能得到这个二维数组。

第一次遇到这个题目的时候，我也是按照上面的思考过程，可惜以上的思维太过僵硬。

后参考别人的文章，得到如下转换公式：

[i,j] = [0,j] - [0,i - 1]

即 区间 [i, j] 之和 = 区间 [0, j] 之和 - 区间 [0, i - 1]之和。

这样就可以缓存0~n之间的和，排列组合有n种，比二维表性能要好很多，因为计算次数大大减少了。

解法版本一

const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);

// 缓存数组
let catchArr = [];

// 初始缓存函数
const catchFn = function () {
    if(catchArr.length === 0) { // catchArr只缓存一次
        let sum = 0;
        for(let i = 0; i < nums.length; i++) {
            sum += nums[i];
            catchArr.push(sum);
        }
    }
}

let sumRange = (i,j) => {
    catchFn();
    return i >= 1 ? catchArr[j] - catchArr[i - 1] : catchArr[j];
}

可以发现，i - 1 存在边界判断,这样每次计算都要判断一次，如果计算10000次，那性能开销会很大。
这里有个小技巧，catchArr[n] 代表的是 0~n 的和，如果在catchArr头部增加一个元素0，那么此时catchArr[n]代表的就是 0 ~ (n-1) 的值，所以此时i~j的区间和就是catch[j+1] - catch[i]。因为i最小值是0，所以不会有边界问题了。得到版本二：

const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);

// 缓存数组
let catchArr = [0];
const catchFn = function () {
    if(catchArr.length === 1) { // catchArr只缓存一次
        let sum = 0;
        for(let i = 0; i < nums.length; i++) {
            sum += nums[i];
            catchArr.push(sum);
        }
    }
}

let sumRange = (i,j) => {
    catchFn();
    return catchArr[j + 1] - catchArr[i];
}

以上代码中，每次调用sumRange()都会执行catchFn，在里面判断是否初始化过，所以可以在第一次初始化之后修改sumRange函数。得到版本三：

const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);

// 缓存数组
let catchArr = [0];
let sumRange;
const catchFn = function () {
    if(catchArr.length === 1) { // catchArr只缓存一次
        let sum = 0;
        for(let i = 0; i < nums.length; i++) {
            sum += nums[i];
            catchArr.push(sum);
        }
              // 重置sumRange函数
              sumRange = (i,j) => catchArr[j + 1] - catchArr[i];
    }
}

sumRange = (i,j) => {
    catchFn();
    return catchArr[j + 1] - catchArr[i];
}

小贴士

除了重置sumRange函数之外，其实将catchFn重置为空函数，一样可以避免if判断，但是js执行空函数，会很耗性能。下图为本人测试结果：

其中需要注意的是：重置sumRange之后，虽然减少了if开销，但是只在百万次以内执行时间减少了，而在百万次之后，反而时间变大，尚切不知道是为什么。

性能测试.png