這幾天都沒有寫Leetcode的總結(jié)，但是其實(shí)我也不是沒有刷題，這幾天主要寫了兩個內(nèi)容的問題，一個部分動態(tài)規(guī)劃，另外一個問題是前綴和。

動態(tài)規(guī)劃：

零錢兌換、零錢兌換II、一和零

動態(tài)規(guī)劃的總結(jié)我發(fā)在Leetcode上面了

https://leetcode-cn.com/problems/coin-change/solution/ling-qian-dui-huan-ling-qian-dui-huan-ii-gpd4/

前綴和：

連續(xù)的子數(shù)組和、和為K的子數(shù)組和、長度最小的子數(shù)組

連續(xù)的子數(shù)組和

這道題需要計算連續(xù)的子數(shù)組的和，而且這個和需要滿足為k的倍數(shù)的特定條件。如果使用暴力方法的話，則需要使用O(n^2)。

我們可以利用前綴和提供的良好的性質(zhì)來處理這個問題。

構(gòu)建一個n+1長度的數(shù)組作為前綴和。遍歷前綴和數(shù)組中的所有元素，如果兩者對于K的余數(shù)相同，這兩者構(gòu)成的數(shù)組是題目需要的子數(shù)組。

在實(shí)際操作的過程中，因為題目要求數(shù)組的長度需要大于等于2。起始的index從1開始即可，但是由于計算前綴和的公式中是sum[j+1] - sum[i] = [i,j]之間數(shù)組的元素和。所以我們index從2開始。并且使用hashset存放取余之后的結(jié)果，如果出現(xiàn)重復(fù)，說明前面有一個元素下標(biāo)為i滿足要求。代碼如下：

和為K的子數(shù)組

看到題目中要求是連續(xù)數(shù)組，則想到可以嘗試前綴和。這道題沒有上面對于數(shù)組長度的限制，長度為一也是可以的。以下面的例子為例，如果當(dāng)前下標(biāo)為j，指向前綴和是第一個出現(xiàn)的6，sum[j+1] - sum[i] == k成立，其實(shí)sum[j+1]輸出的方法數(shù)依賴著sum[i]，所以我們需要存儲每一個元素的方法數(shù)，并且最后的count需要加上sum[i]