標(biāo)注：
本文有參考 別人家的面試題：不可變數(shù)組快速范圍求和
來源：十年蹤跡的博客
本文并非抄襲月影的文章，而是加入了自己的認(rèn)識(shí)。
解題思路:
最笨的實(shí)現(xiàn)方式就是遍歷區(qū)間求和。但是題目要求：
sumRange 可能會(huì)被使用很多次，求不同范圍的值
既然多次使用，為避免重復(fù)計(jì)算，應(yīng)該容易想到緩存計(jì)算結(jié)果。
如何緩存
雖然想到了緩存方案，但具體如何緩存呢，緩存的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是什么樣子？怎么應(yīng)用緩存的結(jié)果？
思考過程：
區(qū)間的取值：
i 的范圍 0 - n，j 的范圍 0 - n。 即 0 ~ i ~ j ~ n;
倒推法：我們要的結(jié)果是區(qū)間范圍 [i,j] 之和，按照直觀的想法，我們很容易想到遍歷 [i,j] 然后累加計(jì)算，然后順著這個(gè)思路，如果采用遍歷累加計(jì)算方案，我們能緩存下來什么？緩存每次的計(jì)算結(jié)果？ 這樣就是查表法了。
可是仔細(xì)想一想，這個(gè)排列組合有多少種？參考下 i,j 的取值范圍，n*n，也就是至少要計(jì)算 n*n 次才能得到這個(gè)二維數(shù)組。
第一次遇到這個(gè)題目的時(shí)候，我也是按照上面的思考過程，可惜以上的思維太過僵硬。
后參考別人的文章，得到如下轉(zhuǎn)換公式：
[i,j] = [0,j] - [0,i - 1]
即 區(qū)間 [i, j] 之和 = 區(qū)間 [0, j] 之和 - 區(qū)間 [0, i - 1]之和。
這樣就可以緩存0~n之間的和，排列組合有n種，比二維表性能要好很多，因?yàn)橛?jì)算次數(shù)大大減少了。
解法版本一
const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);
// 緩存數(shù)組
let catchArr = [];
// 初始緩存函數(shù)
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];
}
可以發(fā)現(xiàn)，i - 1 存在邊界判斷,這樣每次計(jì)算都要判斷一次，如果計(jì)算10000次，那性能開銷會(huì)很大。
這里有個(gè)小技巧，catchArr[n] 代表的是 0~n 的和，如果在catchArr頭部增加一個(gè)元素0，那么此時(shí)catchArr[n]代表的就是 0 ~ (n-1) 的值，所以此時(shí)i~j的區(qū)間和就是catch[j+1] - catch[i]。因?yàn)閕最小值是0，所以不會(huì)有邊界問題了。得到版本二：
const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);
// 緩存數(shù)組
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];
}
以上代碼中，每次調(diào)用sumRange()都會(huì)執(zhí)行catchFn，在里面判斷是否初始化過，所以可以在第一次初始化之后修改sumRange函數(shù)。得到版本三：
const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);
// 緩存數(shù)組
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函數(shù)
sumRange = (i,j) => catchArr[j + 1] - catchArr[i];
}
}
sumRange = (i,j) => {
catchFn();
return catchArr[j + 1] - catchArr[i];
}
小貼士
除了重置sumRange函數(shù)之外，其實(shí)將catchFn重置為空函數(shù)，一樣可以避免if判斷，但是js執(zhí)行空函數(shù)，會(huì)很耗性能。下圖為本人測(cè)試結(jié)果：
其中需要注意的是：重置sumRange之后，雖然減少了if開銷，但是只在百萬次以內(nèi)執(zhí)行時(shí)間減少了，而在百萬次之后，反而時(shí)間變大，尚切不知道是為什么。
