本篇推文共計(jì)2000個(gè)字，閱讀時(shí)間約3分鐘。

題目描述：

給定一個(gè)整數(shù)數(shù)組nums，求出數(shù)組從索引i到j(luò)（i≤j）范圍內(nèi)元素的總和，包含i、j兩點(diǎn)。

實(shí)現(xiàn) NumArray 類(lèi)： 

NumArray(int[] nums) 使用數(shù)組 nums 初始化對(duì)象

int sumRange(int i,int j)

返回?cái)?shù)組 nums 從索引i到j(luò)（i≤j）范圍內(nèi)元素的總和，包含i、j兩點(diǎn)。

也就是 sum(nums[i], nums[i+1],...nums[j])

sumRange會(huì)被反復(fù)調(diào)用無(wú)數(shù)次，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度最低的算法以降低時(shí)間消耗。

示例輸入：

["NumArray","sumRange", "sumRange", "sumRange"]
[[[-2,0,3,-5,2,-1]], [0,2], [2,5],[0,5]]

示例輸出：

[null,1,-1,-3]

示例解釋?zhuān)?/span>

NumArray numArray = new NumArray([-2,0,3,-5,2,-1]);

numArray.sumRange(0, 2); 
return 1
#因?yàn)?(-2)+0+3)=1

numArray.sumRange(2, 5); 
return -1
#因?yàn)?3+(-5)+2 +(-1))=-1

numArray.sumRange(0, 5); 
return -3 
#因?yàn)?(-2)+0+3+(-5)+2+(-1))=-3

看到這題可能很多人會(huì)選擇使用一個(gè)for循環(huán)來(lái)解決，但是請(qǐng)注意題目中強(qiáng)調(diào)的

sumRange會(huì)被反復(fù)調(diào)用無(wú)數(shù)次，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度最低的算法降低時(shí)間消耗

如果使用for循環(huán)解決的話，每次調(diào)用sumRange時(shí)，通過(guò)循環(huán)的方法計(jì)算數(shù)組nums從下標(biāo)i到下標(biāo)j范圍內(nèi)的元素和，需要計(jì)算 j?(i-1) 個(gè)元素的和。

由于每次檢索的時(shí)間和檢索的下標(biāo)范圍有關(guān)，因此檢索的時(shí)間復(fù)雜度較高，如果檢索次數(shù)較多，則會(huì)超出時(shí)間限制。

同時(shí)題目中也強(qiáng)調(diào)sumRange會(huì)多次調(diào)用，如果僅使用for循環(huán)，每次用于檢索的時(shí)間較長(zhǎng)，多次使用后檢索的總時(shí)間就會(huì)增長(zhǎng)的很快。

因此為了降低算法的檢索總時(shí)間,

我們采用前綴和presums的方法解決該題。

前綴和的概念

其實(shí)來(lái)源于sumRange(i,j)的數(shù)學(xué)形式變換

對(duì)公式進(jìn)行變換可得：

所以學(xué)好數(shù)學(xué)很重要?。?！

由此可知，要計(jì)算sumRange(i,j)，

則需要計(jì)算數(shù)組nums在下標(biāo)j和下標(biāo)i-1的前綴和，

然后再計(jì)算兩個(gè)前綴和的差。

同時(shí)如果我們?cè)诤瘮?shù)初始化的時(shí)候

就計(jì)算出數(shù)組nums在每個(gè)下標(biāo)處的前綴和，

即滿(mǎn)足每次調(diào)用sumRange時(shí)的時(shí)間復(fù)雜度都為O(1)

既然理論知識(shí)我們懂了，那么實(shí)際用法如何呢？

假設(shè)數(shù)組nums的長(zhǎng)度為n，創(chuàng)建長(zhǎng)度為n+1的前綴和數(shù)組presums，

對(duì)于0<=i<n，
則有presums[i+1]=presums[i]+nums[i]

對(duì)于0<i<=n，
則presums[i]表示數(shù)組nums從下標(biāo)0到下標(biāo)i-1的前綴和

我們用圖片來(lái)直觀的解釋?zhuān)?/span>

如下圖所示：

設(shè)nums=[0,1,4,6,3,7],presums[0]=0

將前綴和數(shù)組presums的長(zhǎng)度設(shè)為n+1的目的

是為了方便計(jì)算sumRange(i,j)

同時(shí)也不需要對(duì)i=0的情況特殊處理。

所以本題中：

sumRange(i,j)= presums[j+1]- presums[i]

則我們本題的實(shí)現(xiàn)代碼如下：

class NumArray:

    def __init__(self, nums: List[int]):
        self.presums=[0]
        _pre=self.presums
        for num in nums:
            _pre.append(_pre[-1]+num) 

#_pre[-1]+num的含義就是上圖中的+號(hào)步驟，presums中的最后一個(gè)數(shù)與當(dāng)前的nums數(shù)值相加

    def sumRange(self, i: int, j: int) -> int:
        _pre=self.presums
        return _pre[j+1] - _pre[i]