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

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

来自：十年踪迹的博客

链接：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



class extends Sup {

constructor(...args){

super(...args);

Object.freeze(this);



}

}class NumArray extends Immutable(Array){



sumRange(i, j){

let sum = 0;

for(; i



1nums.sumRange(2, 5) -> -1nums.sumRange(0, 5) -> -3

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

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

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

查表

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

二维表？

R/C0123450-2-21-4-2-3103-20-123-20-13-5-3-44215-1二维表可以将每一对 i, j 完全映射一个值，这样的话，空间复杂度变成了 O( n2 )，记得我们前面说了，这个数组可能会很大，有 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;



table.push(sum);



}



sumTable[this.id] = table;



}



sumRange(i, j){

let table = sumTable[this.id];

return table[j + 1] - table;



}



}

})();

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

sumRange(i, j){

let table = sumTable[this.id];

return table[j + 1] - table;



}

来计算出 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;



table.push(sum);



}



sumTable[this.id] = table;



}

let table = sumTable[this.id];

return table[j + 1] - table;



}



}

})();

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

●本文编号341，以后想阅读这篇文章直接输入341即可。

●输入m可以获取到文章目录

相关推荐↓↓↓

Web开发

推荐：《15个技术类公众微信》

涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等

    关注 前端开发