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

来自：十年踪迹的博客

链接：https://www.h5jun.com/post/range-sum-query-immutable.html

这是一道翻译小组的同学问我的题目，这道题很有意思，在 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.id];      
return table[j + 1] - table[i];   
    }
  }
})();

上面的代码里，我们在构造 NumArray 的时候同时创建了一个私有属性 sumTable，它的第 1 个元素是 0，第 i + 1 个元素等于 sumRange(0, i)，因此我们就可以快速通过：

sumRange(i, j){  
let table = sumTable[this.id];  
return table[j + 1] - table[i];   
}

来计算出 sumRange(i, j) 的值了。

进一步优化

上面的代码通过查表大大加快了 sumRange 的执行速度，由于数组 NumArray 是不可变的，因此我们在它被构造的时候创建好 sumTable，那么 sumRange 就完全只需要查表加上一次减法运算就可以完成了。这么做提升了 sumRange 的性能，代价是构造 NumArray 对象的时候带来额外的建表开销。

不过，我们可以不在构造对象的时候建表，而在对象的 sumRange 方法第一次被使用的时候建表。这样的话，我们就将性能开销延从构造对象时迟到了第一次使用 sumRange 时，如果恰巧某种原因，NumArray 对象没有被使用，那么 sumTable 就永远也不会被创建。看下面的代码：

将创建 sumTable 的工作放在 sumRange 第一次被调用时

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)){
    sumRange(i, j){      
if(!sumTable[this.id]){        
let table = [0], sum = 0;        
for(let i = 0; i < this.length; i++){
          sum += this[i];
          table.push(sum);
        }
        sumTable[this.id] = table;
      }      
let table = sumTable[this.id];      
return table[j + 1] - table[i];
    }
  }
})();

以上是今天我们讨论的内容。上面的代码其实还可以优化，因为我们将建表的工作推迟到 sumRange 第一次被调用时执行，这很好，但这给 sumRange 带来了一次 if 判断操作的额外开销，实际上我们应该也有办法消除这个开销，我把这个问题留给大家吧，欢迎大家讨论。