别人家的面试题：不可变数组快速范围求和

点击上方“ 程序员 共读 ”，选择“置顶公众号”

关键时刻，第一时间送达！

这是一道翻译小组的同学问我的题目，这道题很有意思，在 leetcode 上标记的难度为 Easy， 然而正确率出奇地低，只有不到 25%，看来这是一道看似简单实际上颇有挑战性的题目。

不可变数组的范围求和

给定一个整数数组 nums，计算出从第 i 个元素到第 j 个元素的和 ( i ≤ j )，包括 nums[ i ] 和 nums[ j ]。

例子：

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

注意：

1、假定数组的值不会改变（如上面代码，nums 因为 Object.freeze 的缘故可读不可写）

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

3、 数组可能规模很大（比如超过 10000 个数），注意运行时间

解题思路

这道题看起来十分简单对吧，简单写一个函数应该谁都会：

简单实现

function sumRange(i, j){  
var sum = 0;  
for(; i <= j; i++){    sum += nums[i];  }  return sum;}

不过呢，这么写，对照上面的注意事项，尤其是后两条：

• sumRange 可能会被使用很多次

• 数组的规模可能会很大

如果考虑这两条，那么上面的方法可以说是十分慢的，这也是为什么很多人在 leetcode 提交代码通不过，因为简单这么算的话，跑 leetcode 的大数组 case 肯定超时。

那么，我们要怎么做才能更快呢？注意到前面说的这是不可变数组了吧？也就是说数组初始化完成之后，它的值不会改变，因此我们可以对它进行拷贝，同时“重新编码”。

具体怎么做，大家心里是不是已经隐隐有答案了？让我们思考30秒钟然后继续 ——

重构数组

我们可以重新创建一个数组类，用新的数组来计算 sumRange：

重构数组

const Immutable = Sup => class extends Sup {  
constructor(...args){    
super(...args);    
Object.freeze(this);  }}class NumArray extends Immutable(Array){  sumRange(i, j){    
let sum = 0;    
for(; i <= j; i++){      sum += this[i];    }    
return sum;      }}

上面的代码里面我们重构了数组，这里我用了一点点小技巧来让数组元素不可变，这个技巧在我之前的一篇译文“六个漂亮的 ES6 技巧”中被提到，很多同学不理解那篇文章的第6个技巧，在这里我使用了一下，当然这无关我们今天讨论的主题。

于是我们可以用新的数组对象来计算 sumRange：

var nums = new NumArray(-2, 0, 3, -5, 2, -1);nums.sumRange(0, 2) -> 1nums.sumRange(2, 5) -> -1nums.sumRange(0, 5) -> -3

到这里为止，我们似乎并没有改变什么，我们只是继承了 Array 类，把 sumRange 改成了对象的方法而已，它还是一样很慢。

那接下来我们要怎么做呢？

因为前面说过了，sumRange 要被调用很多次，所以我们要尽可能减少 sumRange 调用的复杂度对吗？按照前面的方式，我们用一个循环来对从 i 到 j 进行求和，有没有更快的方法？答案是：空间换时间， 查表！

查表

查表不是查水表，因为 sumRange 要计算很多次，所以我们可以事先在 NumArray 构造的时候将 sumRange 需要查的值算好存入一个表中。

二维表？

二维表可以将每一对 i, j 完全映射一个值，这样的话，空间复杂度变成了 O( n ² )，记得我们前面说了，这个数组可能会很大，有 10000 个元素，如果用这样的映射表，内存就溢出了。实际上，使用 二维表 是愚蠢的，因为我们可以很容易找到以下对应关系：

sumRange(i, j) === sumRange(0, j) - sumRange(0, i - 1); //(i > 0)

一维表

我们只需要将 NumArray 的每一个元素对应从第 1 元素开始求和，将结果保存成一个一维表，我们就可以用 O( 1 ) 时间复杂度来计算 sumRange( i, j ) ！

以下是经过优化之后的 NumArray：

使用一维表

const UniqueID = Sup => class extends Sup {  
constructor(...args){      
super(...args);      
Object.defineProperty(this, "id", {        value: Symbol(),        writable: false,        enumerable: false      });    }}const Immutable = Sup => class extends Sup {  constructor(...args){    
super(...args);    
Object.freeze(this);  }}const NumArray = (function(){  let sumTable = {};  
return class  extends Immutable(UniqueID(Array)){    
constructor(...args){      
super(...args);      
let sum = 0;      
let table = [0];      
for(let i = 0; i < this.length; i++){        sum += this[i];        table.push(sum);      }      sumTable[this.id] = table;    }    sumRange(i, j){      
let table = sumTable[this