(給算法愛好者加星標(biāo)，修煉編程內(nèi)功)

來源：十年蹤跡的博客

h5jun.com/post/range-sum-query-immutable.html

這是一道翻譯小組的同學(xué)問我的題目，這道題很有意思，在 leetcode 上標(biāo)記的難度為 Easy， 然而正確率出奇地低，只有不到 25%，看來這是一道看似簡單實(shí)際上頗有挑戰(zhàn)性的題目。

不可變數(shù)組的范圍求和

給定一個(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) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3

注意：

1、假定數(shù)組的值不會(huì)改變(如上面代碼，nums 因?yàn)?Object.freeze 的緣故可讀不可寫)

2、sumRange 可能會(huì)被使用很多次，求不同范圍的值

3、數(shù)組可能規(guī)模很大(比如超過 10000 個(gè)數(shù))，注意運(yùn)行時(shí)間

解題思路

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

簡單實(shí)現(xiàn)

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

不過呢，這么寫，對照上面的注意事項(xiàng)，尤其是后兩條：

• sumRange 可能會(huì)被使用很多次

• 數(shù)組的規(guī)模可能會(huì)很大

如果考慮這兩條，那么上面的方法可以說是十分慢的，這也是為什么很多人在 leetcode 提交代碼通不過，因?yàn)楹唵芜@么算的話，跑 leetcode 的大數(shù)組 case 肯定超時(shí)。

那么，我們要怎么做才能更快呢？注意到前面說的這是不可變數(shù)組了吧？也就是說數(shù)組初始化完成之后，它的值不會(huì)改變，因此我們可以對它進(jìn)行拷貝，同時(shí)“重新編碼”。

具體怎么做，大家心里是不是已經(jīng)隱隱有答案了？讓我們思考30秒鐘然后繼續(xù) ——

重構(gòu)數(shù)組

我們可以重新創(chuàng)建一個(gè)數(shù)組類，用新的數(shù)組來計(jì)算 sumRange：

重構(gòu)數(shù)組

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ù)組對象來計(jì)算 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 改成了對象的方法而已，它還是一樣很慢。

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

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

查表

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

二維表？

R/C012345

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

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

一維表

我們只需要將 NumArray 的每一個(gè)元素對應(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 對象的時(shí)候帶來額外的建表開銷。

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

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

以上是今天我們討論的內(nèi)容。上面的代碼其實(shí)還可以優(yōu)化，因?yàn)槲覀儗⒔ū淼墓ぷ魍七t到 sumRange 第一次被調(diào)用時(shí)執(zhí)行，這很好，但這給 sumRange 帶來了一次 if 判斷操作的額外開銷，實(shí)際上我們應(yīng)該也有辦法消除這個(gè)開銷，我把這個(gè)問題留給大家吧，歡迎大家討論。

推薦閱讀

(點(diǎn)擊標(biāo)題可跳轉(zhuǎn)閱讀)

從一個(gè)無序數(shù)組中查詢最大值的最快算法是什么？

算法數(shù)據(jù)結(jié)構(gòu)-B樹

覺得本文有幫助？請分享給更多人

關(guān)注「算法愛好者」加星標(biāo)，修煉編程內(nèi)功

好文章，我在看??

總結(jié)

以上是生活随笔為你收集整理的给定数组 求和等于固定值 算法_别人家的面试题：不可变数组快速范围求和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。