摘要：二維表二維表可以將每一對(duì)完全映射一個(gè)值，這樣的話，空間復(fù)雜度變成了，記得我們前面說了，這個(gè)數(shù)組可能會(huì)很大，有個(gè)元素，如果用這樣的映射表，內(nèi)存就溢出了。

給定一個(gè)整數(shù)數(shù)組 nums，計(jì)算出從第 i 個(gè)元素到第 j 個(gè)元素的和 ( i ≤ j )，包括 nums[ i ] 和 nums[ j ]。
例子：

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

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

注意：

假定數(shù)組的值不會(huì)改變（如上面代碼，nums 因?yàn)?Object.freeze 的緣故可讀不可寫）
sumRange 可能會(huì)被使用很多次，求不同范圍的值
數(shù)組可能規(guī)模很大（比如超過 10000 個(gè)數(shù)），注意運(yùn)行時(shí)間

解題思路

這道題看起來十分簡單對(duì)吧，簡單寫一個(gè)函數(shù)應(yīng)該誰都會(huì)：

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;    
  }
}

上面的代碼里面我們重構(gòu)了數(shù)組，這里我用了一點(diǎn)點(diǎn)小技巧來讓數(shù)組元素不可變，這個(gè)技巧在我之前的一篇譯文“六個(gè)漂亮的 ES6 技巧”中被提到，很多同學(xué)不理解那篇文章的第6個(gè)技巧，在這里我使用了一下，當(dāng)然這無關(guān)我們今天討論的主題。

于是我們可以用新的數(shù)組對(duì)象來計(jì)算 sumRange：

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

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

到這里為止，我們似乎并沒有改變什么，我們只是繼承了 Array 類，把 sumRange 改成了對(duì)象的方法而已，它還是一樣很慢。

那接下來我們要怎么做呢？

因?yàn)榍懊嬲f過了，sumRange 要被調(diào)用很多次，所以我們要盡可能減少 sumRange 調(diào)用的復(fù)雜度對(duì)嗎？按照前面的方式，我們用一個(gè)循環(huán)來對(duì)從 i 到 j 進(jìn)行求和，有沒有更快的方法？答案是：空間換時(shí)間，查表！
查表

查表不是查水表，因?yàn)?sumRange 要計(jì)算很多次，所以我們可以事先在 NumArray 構(gòu)造的時(shí)候?qū)?sumRange 需要查的值算好存入一個(gè)表中。

二維表？
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

二維表可以將每一對(duì) i, j 完全映射一個(gè)值，這樣的話，空間復(fù)雜度變成了 O( n2 )，記得我們前面說了，這個(gè)數(shù)組可能會(huì)很大，有 10000 個(gè)元素，如果用這樣的映射表，內(nèi)存就溢出了。實(shí)際上，使用二維表是愚蠢的，因?yàn)槲覀兛梢院苋菀渍业揭韵聦?duì)應(yīng)關(guān)系：

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

一維表

我們只需要將 NumArray 的每一個(gè)元素對(duì)應(yīng)從第 1 元素開始求和，將結(jié)果保存成一個(gè)一維表，我們就可以用 O( 1 ) 時(shí)間復(fù)雜度來計(jì)算 sumRange( i, j ) ！

以下是經(jīng)過優(yōu)化之后的 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];   
    }
  }
})();

上面的代碼里，我們在構(gòu)造 NumArray 的時(shí)候同時(shí)創(chuàng)建了一個(gè)私有屬性 sumTable，它的第 1 個(gè)元素是 0，第 i + 1 個(gè)元素等于 sumRange(0, i)，因此我們就可以快速通過：

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

來計(jì)算出 sumRange(i, j) 的值了。

進(jìn)一步優(yōu)化

上面的代碼通過查表大大加快了 sumRange 的執(zhí)行速度，由于數(shù)組 NumArray 是不可變的，因此我們在它被構(gòu)造的時(shí)候創(chuàng)建好 sumTable，那么 sumRange 就完全只需要查表加上一次減法運(yùn)算就可以完成了。這么做提升了 sumRange 的性能，代價(jià)是構(gòu)造 NumArray 對(duì)象的時(shí)候帶來額外的建表開銷。

不過，我們可以不在構(gòu)造對(duì)象的時(shí)候建表，而在對(duì)象的 sumRange 方法第一次被使用的時(shí)候建表。這樣的話，我們就將性能開銷延從構(gòu)造對(duì)象時(shí)遲到了第一次使用 sumRange 時(shí)，如果恰巧某種原因，NumArray 對(duì)象沒有被使用，那么 sumTable 就永遠(yuǎn)也不會(huì)被創(chuàng)建?？聪旅娴拇a：

將創(chuàng)建 sumTable 的工作放在 sumRange 第一次被調(diào)用時(shí)

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];
    }
  }
})();