币言链语
【coinber app】别人家的面试题：不可变数组快速范围求和
来源：十年踪迹的博客
h5jun.com/post/range-sum-query-immutable.html
这是一道翻译小组的同学问我的题目，这道题很有意思，在 leetcode 上标记的难度为 Easy， 然而正确率出奇地低，只有不到
25%，看来这是一道看似简单实际上颇有挑战性的题目。
不可变数组的范围求和**
给定一个整数数组 nums，计算出从第 i 个元素到第 j 个元素的和 ( i ≤ j )，包括 nums[ i ] 和 nums[ j ]。
例子：
- *
[code]
const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3
[/code]
注意：
1、假定数组的值不会改变（如上面代码，nums 因为 Object.freeze 的缘故可读不可写）
2、sumRange 可能会被使用很多次，求不同范围的值
3、数组可能规模很大（比如超过 10000 个数），注意运行时间
解题思路**
这道题看起来十分简单对吧，简单写一个函数应该谁都会：
简单实现
[code]
function sumRange(i, j){ var sum = 0; for(; i <= j; i++){ sum += nums[i]; } return sum;}
[/code]
不过呢，这么写，对照上面的注意事项，尤其是后两条：
*sumRange 可能会被使用很多次
*数组的规模可能会很大
如果考虑这两条，那么上面的方法可以说是十分慢的，这也是为什么很多人在 leetcode 提交代码通不过，因为简单这么算的话，跑 leetcode 的大数组
case 肯定超时。
那么，我们要怎么做才能更快呢？注意到前面说的这是不可变数组了吧？也就是说数组初始化完成之后，它的值不会改变，因此我们可以对它进行拷贝，同时“重新编码”。
具体怎么做，大家心里是不是已经隐隐有答案了？让我们思考 30 秒钟然后继续 ——
重构数组**
我们可以重新创建一个数组类，用新的数组来计算 sumRange：
重构数组
[code]
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; }}
[/code]
[code]
上面的代码里面我们重构了数组，这里我用了一点点小技巧来让数组元素不可变，这个技巧在我之前的一篇译文“六个漂亮的 ES6 技巧”中被提到，很多同学不理解那篇文章的第 6 个技巧，在这里我使用了一下，当然这无关我们今天讨论的主题。
[/code]
于是我们可以用新的数组对象来计算 sumRange：
- *
[code]
var nums = new NumArray(-2, 0, 3, -5, 2, -1);nums.sumRange(0, 2) -> 1nums.sumRange(2, 5) -> -1nums.sumRange(0, 5) -> -3
[/code]
到这里为止，我们似乎并没有改变什么，我们只是继承了 Array 类，把 sumRange 改成了对象的方法而已，它还是一样很慢。
那接下来我们要怎么做呢？
因为前面说过了，sumRange 要被调用很多次，所以我们要尽可能减少 sumRange 调用的复杂度对吗？按照前面的方式，我们用一个循环来对从 i 到 j
进行求和，有没有更快的方法？答案是：空间换时间，查表！
查表**
查表不是查水表，因为 sumRange 要计算很多次，所以我们可以事先在 NumArray 构造的时候将 sumRange 需要查的值算好存入一个表中。
二维表？
| R/C | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | -2 | -2 | 1 | -4 | -2 | -3 |
| 1 | ||||||
| 0 | 3 | -2 | 0 | -1 | ||
| 2 | ||||||
| 3 | -2 | 0 | -1 | |||
| 3 | ||||||
| -5 | -3 | -4 | ||||
| 4 | ||||||
| 2 | 1 | |||||
| 5 | ||||||
| -1 | ||||||
| 二维表可以将每一对 i, j 完全映射一个值，这样的话，空间复杂度变成了 O( n2 )，记得我们前面说了，这个数组可能会很大，有 10000 | ||||||
| 个元素，如果用这样的映射表，内存就溢出了。实际上，使用二维表是愚蠢的，因为我们可以很容易找到以下对应关系： |
*
[code]
sumRange(i, j) === sumRange(0, j) - sumRange(0, i - 1); //(i > 0)
[/code]
一维表
我们只需要将 NumArray 的每一个元素对应从第 1 元素开始求和，将结果保存成一个一维表，我们就可以用 O( 1 ) 时间复杂度来计算
sumRange( i, j ) ！
以下是经过优化之后的 NumArray：
使用一维表
[code]
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]; } }})();
[/code]
上面的代码里，我们在构造 NumArray 的时候同时创建了一个私有属性 sumTable，它的第 1 个元素是 0，第 i + 1 个元素等于
sumRange(0, i)，因此我们就可以快速通过：
[code]
sumRange(i, j){ let table = sumTable[this.id]; return table[j + 1] - table[i]; }
[/code]
来计算出 sumRange(i, j) 的值了。
进一步优化**
上面的代码通过查表大大加快了 sumRange 的执行速度，由于数组 NumArray 是不可变的，因此我们在它被构造的时候创建好 sumTable，那么
sumRange 就完全只需要查表加上一次减法运算就可以完成了。这么做提升了 sumRange 的性能，代价是构造 NumArray
对象的时候带来额外的建表开销。
不过，我们可以不在构造对象的时候建表，而在对象的 sumRange 方法第一次被使用的时候建表。这样的话，我们就将性能开销延从构造对象时迟到了第一次使用
sumRange 时，如果恰巧某种原因，NumArray 对象没有被使用，那么 sumTable 就永远也不会被创建。看下面的代码：
将创建 sumTable 的工作放在 sumRange 第一次被调用时
[code]
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]; } }})();
[/code]
以上是今天我们讨论的内容。上面的代码其实还可以优化，因为我们将建表的工作推迟到 sumRange 第一次被调用时执行，这很好，但这给 sumRange
带来了一次 if 判断操作的额外开销，实际上我们应该也有办法消除这个开销，我把这个问题留给大家吧，欢迎大家讨论。
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：juu3644。
