網(wǎng)絡(luò)做翻譯的網(wǎng)站愛站seo綜合查詢
目錄
題目一：一維前綴和[模版]
題目二：二維前綴和[模版]
題目三：尋找數(shù)組的中心下標(biāo)
題目四：除自身以外數(shù)組的乘積
題目五：和為K的子數(shù)組
題目六：和可被K整除的子數(shù)組
題目七：連續(xù)數(shù)組
題目八：矩陣區(qū)域和
題目一：一維前綴和[模版]
示例1
輸入：
3 2 1 2 4 1 2 2 3
輸出：
3 6
題目要求是：給一個(gè)數(shù)組，需要注意的是：下標(biāo)是從1開始
查詢時(shí)給下標(biāo)l和r，返回下標(biāo)從l到下標(biāo)為r的元素的和
也就是：如果數(shù)組arr是[2, 4, 6]，那么查詢時(shí)如果是：1? 2，那就返回6(2+4)，如果是2? 3，就返回10(4+6)，如果是1 3，就返回12(2+4+6)
解法一：暴力解法
暴力解法很簡單，即就是題目需要求哪段區(qū)間的和，那我就從這個(gè)區(qū)間的開始一直加到這個(gè)區(qū)間的結(jié)尾即可
時(shí)間復(fù)雜度：O(N*q)
假設(shè)每次詢問的查詢范圍都是從頭找到尾，所以是O(N)的，而q次詢問，所以是O(q)，嵌套起來就是O(N*q)
而這道題N和q的范圍都是從1到10^5的，最差的情況，時(shí)間復(fù)雜度是10^10，是絕對會超時(shí)的
解法二：前綴和
前綴和：快速求出數(shù)組中某一個(gè)連續(xù)區(qū)間的和
這里的快速指查找時(shí)間復(fù)雜度為O(1)，但是預(yù)處理一個(gè)前綴和數(shù)組的時(shí)間復(fù)雜度為O(N)，所以使用前綴和后，時(shí)間復(fù)雜度變?yōu)镺(N) + O(q)了，之所以不是相乘是因?yàn)檫@兩個(gè)過程并沒有嵌套在一起進(jìn)行
要想使用前綴和，分為下面兩步：
①預(yù)處理出來一個(gè)前綴和數(shù)組
數(shù)組有幾個(gè)元素，前綴和數(shù)組dp就有幾個(gè)元素
dp[i]就表示[1, i]區(qū)間內(nèi)所有元素的和
也就是如果數(shù)組arr是[1, 2, 3]，那么dp數(shù)組就是[1, 3, 6]
這里可以優(yōu)化的一點(diǎn)是：每次算前i個(gè)數(shù)的和，不需要從1開始加，從i-1開始加即可，因?yàn)閕-1位置的元素就表示前i-1個(gè)元素的和
所以dp[i]的公式是：dp[i] = dp[i+1] + arr[i]
②使用前綴和數(shù)組
使用前綴和數(shù)組也很簡單：
即如果查找的是3~5區(qū)間的和，那么只需要使用dp[5] - dp[2]，即就是下標(biāo)為1~5的和，減去1~2的和，算出來就是3~5的和了
即就是查找[l, r]區(qū)間的和，則dp[r] - dp[l - 1]即可
下面講個(gè)細(xì)節(jié)問題，為什么下標(biāo)要從1開始計(jì)數(shù)
如果計(jì)算的是計(jì)算的是前兩個(gè)元素的和，公式就變?yōu)榱?#xff1a;dp[2] - dp[-1]，這就會導(dǎo)致越界訪問了，所以這種情況還需要處理邊界情況，麻煩一些
而如果下標(biāo)是從1開始的，那么如果計(jì)算的是前兩個(gè)元素的和就是：dp[2] - dp[0]，我們只需將dp數(shù)組中dp[0]的值置為0就能完美解決這個(gè)問題
代碼如下：
#include <iostream>
#include <vector>
using namespace std;int main() {int n = 0,q = 0;cin >> n >> q;//讀入數(shù)據(jù)vector<int> arr(n+1);vector<long long> dp(n+1);//防止溢出//預(yù)處理出來一個(gè)前綴和數(shù)組for(int i = 1; i < arr.size(); i++){cin >> arr[i];dp[i] = dp[i-1] + arr[i];}//使用前綴和數(shù)組int l = 0, r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] << endl;}return 0;
}題目二：二維前綴和[模版]
示例1
輸入：
3 4 3 1 2 3 4 3 2 1 0 1 5 7 8 1 1 2 2 1 1 3 3 1 2 3 4
輸出：
8 25 32
上述題目一是一維的前綴和，題目二是二維的前綴和
就以示例一來說明題意：
第一行的 3 4 3，表示有一個(gè)3行4列的矩陣，查詢次數(shù)是3次
3行4列的矩陣為接下來輸入的3行數(shù)據(jù)，即：
最后三行就表示所查詢的三次內(nèi)容，前兩個(gè)數(shù)字表示一個(gè)坐標(biāo)，后兩個(gè)數(shù)字表示一個(gè)坐標(biāo)
即1 1 2 2就表示(1,1)到(2,2)的這個(gè)矩形范圍所有值的和，即下圖紅色區(qū)域：
解法一：暴力解法
每次詢問時(shí)，都給出整個(gè)區(qū)間所有元素的和，因?yàn)槭莔行n列q此詢問，所以時(shí)間復(fù)雜度是O(m*n*q)，因?yàn)槊看卧儐栕畈钋闆r都要遍歷數(shù)組一遍，是O(m*q)，而詢問q次，是嵌套關(guān)系，所以是O(m*n*q)
當(dāng)然了，在看到這個(gè)時(shí)間復(fù)雜度后，我們就很容易可以判斷出來，這個(gè)時(shí)間肯定超時(shí)了，所以接下來看解法二
解法二：前綴和
同樣是分為兩步
①預(yù)處理出前綴和矩陣
同樣重新創(chuàng)建一個(gè)和原始矩陣相同規(guī)模的矩陣，不同的是新矩陣dp，每一個(gè)位置dp[i, j]表示的含義是：從[1, 1]到[i, j]這個(gè)位置所有元素的和
例如下圖，如果想求這個(gè)矩陣中所有元素的和，那么可以分為下面四部分：
我們加入想求[1, 1]到[i, j]位置所有元素的和，只需要求A + B + C + D即可，也就是將ABCD這四個(gè)區(qū)域的元素之和相加，但是A好求，B、C不太好求，所以可以退而求其次，求A + B和A + C的值，此時(shí)多加了一遍A，只需最后減去即可，所以：
dp[i,j] = (A + B) + (A + C) + D - A = dp[i][j-1] + dp[i-1][j] + arr[i,j] - dp[i-1][j-1]
此時(shí)求dp[i,j]的時(shí)間復(fù)雜度就是O(1)的
②使用前綴和矩陣
所以按照上面的思想，如果想要求[x1, y1] ~ [x2, y2]的區(qū)域的元素和，也就是下面的D區(qū)域：
此時(shí)求D區(qū)域，就可以整體的A+B+C+D，再減去A+B+C，但是單獨(dú)的B和C不好算，所以依舊使用A+B和B+C來計(jì)算，因?yàn)槎鄿p了一次A，所以最后再加上多減的那個(gè)A即可，公式即為：
dp[x2, y2] - dp[x1-1, y2] - dp[x2, y1-1] + dp[x1-1, y1-1]
根據(jù)上圖可以輕松寫出
由于需要先構(gòu)建m行n列前綴和數(shù)組dp，所以時(shí)間復(fù)雜度是O(m*n)，又因?yàn)槊看尾樵冎恍枰滓粋€(gè)公式，所以時(shí)間復(fù)雜度為O(1)，需要查詢q次，所以前綴和的時(shí)間復(fù)雜度為：O(m*n) + O(q)
上述第一個(gè)公式用于預(yù)處理出前綴和矩陣，第二個(gè)公式用于使用前綴和矩陣
代碼如下：
#include <iostream>
#include <vector>
using namespace std;int main()
{//輸入數(shù)據(jù)int n = 0,m = 0,q = 0;cin >> n >> m >> q;vector<vector<int>> arr(n+1,vector<int>(m+1));for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> arr[i][j];//預(yù)處理前綴和矩陣vector<vector<long long>> dp(n+1,vector<long long>(m+1));//long long防止溢出for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];//使用前綴和矩陣dpint x1 = 0, y1 = 0, x2 = 0, y2 = 0;while(q--){cin >> x1 >> y1 >> x2 >> y2;cout << (dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]) << endl;}return 0;
}題目三：尋找數(shù)組的中心下標(biāo)
給你一個(gè)整數(shù)數(shù)組?nums?，請計(jì)算數(shù)組的?中心下標(biāo)?。
數(shù)組?中心下標(biāo)?是數(shù)組的一個(gè)下標(biāo)，其左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。
如果中心下標(biāo)位于數(shù)組最左端，那么左側(cè)數(shù)之和視為?0?，因?yàn)樵谙聵?biāo)的左側(cè)不存在元素。這一點(diǎn)對于中心下標(biāo)位于數(shù)組最右端同樣適用。
如果數(shù)組有多個(gè)中心下標(biāo)，應(yīng)該返回?最靠近左邊?的那一個(gè)。如果數(shù)組不存在中心下標(biāo)，返回?-1?。
示例 1：
輸入：nums = [1, 7, 3, 6, 5, 6] 輸出：3 解釋： 中心下標(biāo)是 3 。 左側(cè)數(shù)之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ， 右側(cè)數(shù)之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
輸入：nums = [1, 2, 3] 輸出：-1 解釋： 數(shù)組中不存在滿足此條件的中心下標(biāo)。
示例 3：
輸入：nums = [2, 1, -1] 輸出：0 解釋： 中心下標(biāo)是 0 。 左側(cè)數(shù)之和 sum = 0 ，（下標(biāo) 0 左側(cè)不存在元素）， 右側(cè)數(shù)之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
解法一：暴力解法
每次枚舉一個(gè)位置，都去將這個(gè)位置的左邊和右邊的元素都累加，去比較總和是否相同，這里的暴力解法的時(shí)間復(fù)雜度是O(N^2)的
因?yàn)槊杜e下標(biāo)是O(N)，求和也是O(N)，所以是時(shí)間復(fù)雜度是O(N^2)
解法二：前綴和
此題使用的依舊是前綴和的思路，與前面不同的是，此題要求中心下標(biāo)的左邊元素和右邊元素相加的和是相同的，所以這里可以引出前綴和數(shù)組 f 和后綴和數(shù)組 g
這里的前綴和數(shù)組的定義與前面的前綴和數(shù)組的定義是不同的，并不包含當(dāng)前位置的值，所以也就進(jìn)一步的說明，前綴和數(shù)組只是一個(gè)思想，并不是一個(gè)固定的格式
f[i] 表示從0加到i-1位置的元素和，g[i] 表示從i+1加到n-1位置的元素和
同樣是分為下面的兩步：
①預(yù)處理出前綴和、后綴和數(shù)組
首先我們明白，在此題中，f[i]表示 0 ~ i - 1 位置的元素的和，所以f[i-1]就是0~i-2位置的元素的和，還差一個(gè)nums[i-1]，再加上即可，g[i]同理可得：
f[i] = f[i-1] + nums[i-1]
g[i] = g[i+1] + nums[i+1]
②使用前綴和、后綴和數(shù)組
在上面預(yù)處理出前綴和與后綴和數(shù)組后，只需枚舉每個(gè)下標(biāo)時(shí)，判斷f[i]與g[i]是否相等即可，如果相等就表示該下標(biāo)是數(shù)組的中心下標(biāo)
下面是此題需要注意的兩個(gè)細(xì)節(jié)問題：
第一、f[0]與g[n-1]都需要提前處理，因?yàn)槿绻惶幚?#xff0c;f[0]的公式會出現(xiàn)f[-1]，g[n-1]的公式會出現(xiàn)g[n]，這兩種情況都是導(dǎo)致越界訪問
第二、預(yù)處理前綴和數(shù)組需要從左向右處理，而預(yù)處理后綴和數(shù)組則需要從后向前處理，因?yàn)榍熬Y和數(shù)組計(jì)算時(shí)，每一個(gè)位置都需要前一個(gè)位置的值，而后綴和數(shù)組每一個(gè)位置都需要后一個(gè)位置的值
代碼如下：
class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n);vector<int> g(n);//預(yù)處理前綴和數(shù)組f，從下標(biāo)1開始，下標(biāo)0默認(rèn)值是0for(int i = 1; i < n; i++)f[i] = f[i-1] + nums[i-1];//預(yù)處理后綴和數(shù)組g，從下標(biāo)n-2開始，下標(biāo)n-1默認(rèn)值是0for(int i = n - 2; i >= 0; i--)g[i] = g[i+1] + nums[i+1];//使用數(shù)組for(int i = 0; i < n; i++)if(f[i] == g[i]) return i;return -1;}
};題目四：除自身以外數(shù)組的乘積
給你一個(gè)整數(shù)數(shù)組?nums，返回?數(shù)組?answer?，其中?answer[i]?等于?nums?中除?nums[i]?之外其余各元素的乘積?。
題目數(shù)據(jù)?保證?數(shù)組?nums之中任意元素的全部前綴元素和后綴的乘積都在??32 位?整數(shù)范圍內(nèi)。
請?不要使用除法，且在?O(n)?時(shí)間復(fù)雜度內(nèi)完成此題。
示例 1:
輸入: nums =[1,2,3,4]輸出:[24,12,8,6]
示例 2:
輸入: nums = [-1,1,0,-3,3] 輸出: [0,0,9,0,0]
此題題意是比較好理解的， 例如示例一，數(shù)組nums元素是1、2、3、4，返回一個(gè)數(shù)組answer，在數(shù)組answer中，每一個(gè)元素的值都是nums中除了該位置的數(shù)外，其余所有元素的乘積，如下所示：
nums元素是[1, 2, 3, 4]，所以answer數(shù)組中的第一個(gè)元素值為：2*3*4=24，第二個(gè)元素值為1*3*4=12，第三個(gè)元素值為：1*2*4=8，第四個(gè)元素的值為：1*2*3=6
所以answer數(shù)組的元素就為：[24, 12, 8, 6]
解法一：暴力解法
暴力解法也很簡單，依次枚舉每個(gè)位置，然后再求除了該位置外的所有元素的乘積，時(shí)間復(fù)雜度是O(N^2)的
因?yàn)槊杜e每個(gè)位置的時(shí)間復(fù)雜度是O(N)，而其中還需要嵌套一個(gè)循環(huán)，是遍歷其余元素，求其余元素的乘積，時(shí)間復(fù)雜度也是O(N)，所以總的時(shí)間復(fù)雜度是O(N^2)
解法二：前綴積 + 后綴積
此題同樣是需要使用前綴和的思想，但是每道題的前綴和處理思路都是根據(jù)實(shí)際情況來定的，此題中需要求一個(gè)answer數(shù)組，使得該數(shù)組的每一個(gè)元素的值都是nums數(shù)組中其余元素的乘積
所以如果要求i位置的值，就需要知道 0 ~ i-1 位置的元素的乘積，以及 i+1 ~ n-1 位置的元素的乘積，所以此題實(shí)際的解法可以稱之為前綴積
根據(jù)上述的描述，我們可以知道，想要得到所需的answer數(shù)組，需要 i 下標(biāo)之前的前綴積和 i 下標(biāo)之后的后綴積
同樣是分為下面的兩步：
①預(yù)處理出前綴積、后綴積數(shù)組
前綴積數(shù)組用 f 表示，后綴積數(shù)組用 g 表示
f[i] 表示[0,?i-1]區(qū)間內(nèi)所有元素的積，
f[i] = f[i-1] * nums[i-1]
g[i] 表示[i+1, n-1]區(qū)間內(nèi)所有元素的積，
g[i] = g[i+1] * nums[i+1]
②使用前綴積、后綴積數(shù)組
由于此題所要求的是得出一個(gè)answer數(shù)組，所以只需創(chuàng)建出一個(gè)大小與nums相同的數(shù)組，數(shù)組中每個(gè)元素都使用 f[i] * g[i]來得出最后的值
同樣這里也有需要注意的細(xì)節(jié)問題
與上一題一樣，f[0] 和 g[n-1] 都有可能出現(xiàn)越界訪問的問題
因?yàn)?f[1] = f[0] * nums[0]，而f[1]本身就應(yīng)該等于 nums[0]，1乘任意一個(gè)數(shù)還等于這個(gè)數(shù)，所以這里初始化 f[0] 為1，g[n-1]同理可得，也初始化為1
代碼如下：
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> answer(n);//預(yù)處理前綴積數(shù)組 f 和后綴積數(shù)組 gvector<int> f(n), g(n);f[0] = g[n-1] = 1; // 處理細(xì)節(jié)問題for(int i = 1; i < n; i++)f[i] = f[i-1] * nums[i-1];for(int i = n - 2; i >= 0; i--)g[i] = g[i+1] * nums[i+1];//使用前綴積和后綴積數(shù)組for(int i = 0; i < n; i++)answer[i] = f[i] * g[i];return answer;}
};題目五：和為K的子數(shù)組
給你一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k?，請你統(tǒng)計(jì)并返回?該數(shù)組中和為?k?的子數(shù)組的個(gè)數(shù)?。
子數(shù)組是數(shù)組中元素的連續(xù)非空序列。
示例 1：
輸入：nums = [1,1,1], k = 2 輸出：2
示例 2：
輸入：nums = [1,2,3], k = 3 輸出：2
解法一：暴力解法
此題看題意，很容易想出暴力解法，即從第一個(gè)位置開始，依次向后枚舉，一直累加，因?yàn)榭赡艽嬖谪?fù)數(shù)，所以每次都需要加到最后一個(gè)元素，第一個(gè)位置累加完畢，就從第二個(gè)位置加，加到最后一個(gè)元素位置，直到最后一個(gè)元素
暴力枚舉可以將數(shù)組中可能存在的子數(shù)組枚舉一遍，每次判斷子數(shù)組的元素和是否等于k，從而解答此題
暴力枚舉的時(shí)間復(fù)雜度是O(N^2)
根據(jù)上述所說，可能存在負(fù)數(shù)的情況，所以這里的數(shù)組是不具備單調(diào)性的，所以也就不能使用雙指針(滑動窗口)優(yōu)化
解法二：前綴和 + 哈希表
想要使用前綴和的思想，我們可以將子數(shù)組轉(zhuǎn)變?yōu)橐?i 位置為結(jié)尾的子數(shù)組，暴力解法是以 i 位置為開頭的所有子數(shù)組，這兩種遍歷方式?jīng)]有區(qū)別，一個(gè)是從前向后遍歷，一個(gè)是從后向前遍歷的
之所以使用以 i 結(jié)尾，是因?yàn)檫@樣可以更好的使用前綴和的思想，因?yàn)榇藭r(shí)可以預(yù)處理出前綴和數(shù)組sum，sum[i]就表示 i 之前的所有元素的和
因?yàn)樾枰以刂蜑閗的子數(shù)組，而如果我們以i為結(jié)尾，從i開始遍歷向前找和為k的子數(shù)組，那和暴力解法沒區(qū)別，所以此時(shí)可以轉(zhuǎn)換思路：
尋找和為k的子數(shù)組，當(dāng)枚舉到 i 位置后，我們可以根據(jù)sum[i]知道以 i 位置為結(jié)尾的數(shù)組前綴和是多少，那么想找到一個(gè)子數(shù)組的元素和為k，可以轉(zhuǎn)換為：
當(dāng)我們枚舉到以 i 位置為結(jié)尾時(shí)，想找一個(gè)子數(shù)組，它的前綴和為sum[i] - k即可，如果能夠找到一個(gè)子數(shù)組的前綴和為sum[i] - k，那么就變相的說明i之前的數(shù)組中，存在和為k的子數(shù)組，相當(dāng)于將i結(jié)尾的數(shù)組分為了兩部分，一部分是和為k的子數(shù)組，一部分是和為sum[i] - k的子數(shù)組
也就是說，我們想找和為k的A數(shù)組，轉(zhuǎn)化思路后變?yōu)檎业胶蜑閟um[i]-k的B數(shù)組，也就相當(dāng)于找到了和為k的A數(shù)組
即需要找到在[0, i-1]這個(gè)區(qū)間中，有多少個(gè)前綴和為 sum[i] - k的子數(shù)組
那么在了解這個(gè)思想后，我們難道是直接創(chuàng)建一個(gè)前綴和數(shù)組，再找i位置之前有多少個(gè)子數(shù)組的和等于sum[i] - k嗎，那么此時(shí)這個(gè)算法的時(shí)間復(fù)雜度也是O(N^2)，依舊是遍歷數(shù)組的思路
因?yàn)楸闅vi位置是O(N)，再尋找和為sum[i] - k也是O(N)，所以時(shí)間復(fù)雜度也是O(N^2)，那么如何巧妙地解決這個(gè)問題呢，這里就需要用到哈希表這個(gè)思想了：
哈希表就是用于快速查找某個(gè)數(shù)的，所以我們可以將前綴和插入到哈希表里，統(tǒng)計(jì)前綴和出現(xiàn)的次數(shù)，所以哈希表存的就是int, int類型的，第一個(gè)int存的是前綴和，第二個(gè)int存的是前綴和出現(xiàn)的次數(shù)，此時(shí)就無需遍歷數(shù)組尋找和為sum[i] - k的數(shù)組，只需要找哈希表中sum[i] - k所對應(yīng)的數(shù)字即可
?下面是細(xì)節(jié)問題：
①前綴和何時(shí)放入哈希表中？
是創(chuàng)建出前綴和數(shù)組，一股腦全放進(jìn)去嗎？是不能一開始就全放進(jìn)哈希表中的，因?yàn)槲覀兯?jì)算的是 i 位置之前有多少個(gè)前綴和等于sum[i] - k，如果全放進(jìn)入，是可能會統(tǒng)計(jì)到 i 位置之后的某些位置的前綴和數(shù)組也可能等于sum[i] - k
因此在計(jì)算 i 位置之前，哈希表中只保存 0~i-1 位置的前綴和
②不用真的創(chuàng)建出來一個(gè)前綴和數(shù)組
因?yàn)槊看蝑p[i] = dp[i-1] + nums[i-1]，每次只需要知道前一個(gè)位置的前綴和即可，所以此題中，只需使用一個(gè)變量sum標(biāo)記之前的元素前綴和dp[i-1]是多少，計(jì)算完dp[i]后，把sum更新為dp[i]即可，所以在計(jì)算下一個(gè)dp[i]的時(shí)候，這個(gè)sum依舊是計(jì)算前的前綴和的值
③整個(gè)前綴和等于k的情況
也就是 0~i 這段區(qū)域的區(qū)間等于k，此時(shí)如果出現(xiàn)這種情況，我們按照上面的描述，就會在[0, -1]的區(qū)間內(nèi)尋找，但是這個(gè)區(qū)間并不存在，而我們此時(shí)是存在這個(gè)等于k的情況的，所以需要特殊處理這種情況，因?yàn)檎麄€(gè)數(shù)組的和為k，我們想找的sum[i] - k就變?yōu)?了，所以此時(shí)需要先設(shè)置hash[0] = 1，先在哈希表中存入這種情況
代碼如下：
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> hash;//統(tǒng)計(jì)前綴和出現(xiàn)的次數(shù)hash[0] = 1; //處理整個(gè)數(shù)組之和是k的情況int sum = 0, ret = 0;for(auto& it : nums){sum += it;//計(jì)算當(dāng)前位置的前綴和if(hash.count(sum - k)) ret += hash[sum - k];//統(tǒng)計(jì)個(gè)數(shù)hash[sum]++;//將當(dāng)前位置的前綴和放入哈希表中}return ret; }
};題目六：和可被K整除的子數(shù)組
給定一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k?，返回其中元素之和可被?k?整除的（連續(xù)、非空）?子數(shù)組?的數(shù)目。
子數(shù)組?是數(shù)組的?連續(xù)?部分。
示例 1：
輸入：nums = [4,5,0,-2,-3,1], k = 5 輸出：7 解釋： 有 7 個(gè)子數(shù)組滿足其元素之和可被 k = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:
輸入: nums = [5], k = 9 輸出: 0
首先這道題在做之前，先解釋兩個(gè)數(shù)學(xué)知識：
①同余定理
同余定理指的是，如果 (a - b) / p = k .... 0，也就是說 (a - b) 能夠整除 k，那就存在a%p == b%p
證明很簡單，(a - b) = k*p? ->? a = b + k*p -> a % p = b % p
因?yàn)閗*p % p = 0，所以得出上式
②負(fù)數(shù)除以整數(shù)的情況
舉個(gè)例子： -4 % 3 ==?-1，但是在數(shù)學(xué)上，余數(shù)只有正的，所以如果想取得正余數(shù)，余數(shù)無論正負(fù)數(shù)的通用公式如下：
(a % p + p) % p
因?yàn)樨?fù)數(shù)%正數(shù)，得出的結(jié)果是負(fù)數(shù)，如果想要正數(shù)就需要加上這個(gè)正數(shù)，又因?yàn)榭赡茉镜慕Y(jié)果就是正數(shù)，此時(shí)再%這個(gè)正數(shù)，如果原本就是正數(shù)的話，后面加的這個(gè)p就被抵消了
解法一：暴力解法
暴力枚舉出所有的子數(shù)組，然后把子數(shù)組的和加起來，判斷是否能被k整除，與上一題一樣，此題依舊是不能使用滑動窗口來做優(yōu)化的，因?yàn)榭赡艽嬖谪?fù)數(shù)，數(shù)組不是單調(diào)的
解法二：前綴和 + 哈希表
這道題和上一題同樣的思想，使用前綴和 + 哈希表完成
同樣是求i之前的子數(shù)組的元素之和能夠整除k，也就是下圖所示：
假設(shè)在 i 之前的這段綠色區(qū)域的元素之和，能夠被 k 整除，而前面這段紅色區(qū)域元素之和是 x
所以得到： (sum - x) % k = 0，根據(jù)同余定理，可以得到：sum % k == x % k
所以得到一個(gè)結(jié)論，如果后面的綠色區(qū)域能夠被 k 整除，那么前面的這段紅色區(qū)域，同樣能被 k 整除，那么也就是說，在 [0, i-1] 這個(gè)區(qū)間內(nèi)，有多少個(gè)前綴和的余數(shù)是sum % k的，就說明有多少個(gè)子數(shù)組是滿足被 k 整除這個(gè)條件的
同樣需要處理細(xì)節(jié)問題，其他和上一題一樣，唯一有一個(gè)需要注意的是：哈希表同樣是<int, int>，但是第一個(gè)int不是存的前綴和了，而是存的前綴和的余數(shù)
代碼如下：
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int ,int> hash;hash[0] = 1; //特殊情況，如果整體的前綴和能被k整除int sum = 0, ret = 0;for(auto& it : nums){sum += it; //sum算出當(dāng)前位置之前的前綴和int ans = (sum % k + k) % k; //求出修正后的余數(shù)if(hash.count(ans)) ret += hash[ans]; //統(tǒng)計(jì)結(jié)果hash[ans]++;}return ret;}
};題目七：連續(xù)數(shù)組
給定一個(gè)二進(jìn)制數(shù)組?nums?, 找到含有相同數(shù)量的?0?和?1?的最長連續(xù)子數(shù)組，并返回該子數(shù)組的長度。
示例 1:
輸入: nums = [0,1] 輸出: 2 說明: [0, 1] 是具有相同數(shù)量 0 和 1 的最長連續(xù)子數(shù)組。
示例 2:
輸入: nums = [0,1,0] 輸出: 2 說明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。
首先先看這個(gè)題目要求，找含有相同數(shù)量的0和1的最長連續(xù)子數(shù)組，我們初始看這個(gè)題目要求感覺可能半天想不出來解法， 但是如果轉(zhuǎn)換一下思路，將數(shù)組中的0全部換為-1，此時(shí)就變?yōu)榱俗訑?shù)組中含有的1和-1的數(shù)量相同，那如果1和-1的數(shù)量相同，就說明相加為0了，此時(shí)就可以和前面的和為k的子數(shù)組那道題一樣了，這道題就變?yōu)榱?#xff1a;和為0的最長子數(shù)組了
雖然思想是一樣的，但是卻是有很多細(xì)節(jié)問題，如下所示：
①哈希表中存什么
哈希表同樣是int, int，第一個(gè)int存的依然是前綴和，但是這里的第二個(gè)int存的是下標(biāo)，因?yàn)樾枰肋@里的下標(biāo)，才能算出這里的下標(biāo)與
②什么時(shí)候存入哈希表
和上一題一樣，都是在計(jì)算 i 位置之前，哈希表中只保存 0~i-1 位置的前綴和
③如果哈希表中出現(xiàn)重復(fù)的<sum, i>時(shí)，如何存
存的是第一次出現(xiàn)的值，因?yàn)槿缦聢D所示，綠色是符合要求的區(qū)域，而越早出現(xiàn)的符合要求的點(diǎn)越靠左，越靠左綠色的范圍就越大， 即子數(shù)組的長度越長
因?yàn)榇藭r(shí)符合要求的子數(shù)組相加為0，所以左邊的紅色區(qū)域的和也就是sum，因此符合的點(diǎn)越靠左，綠色區(qū)域越大，即符合要求的子數(shù)組長度越長
④默認(rèn)的整體的數(shù)組前綴和為0，如何存
因?yàn)槿绻趇位置之前有一個(gè)子數(shù)組滿足條件，那么是在0~i-1的區(qū)域找滿足條件的子數(shù)組，而此時(shí)整個(gè)數(shù)組都滿足題意了，那么在前面就沒有位置找了，所以就變成了在[0, -1]的區(qū)間找
當(dāng)數(shù)組整體前綴和為0時(shí)，我們就需要在-1的位置尋找一個(gè)前綴和，因?yàn)榇娴氖窍聵?biāo)，所以存的是-1，所以此時(shí)計(jì)算長度時(shí)就能夠滿足這種特殊情況了
⑤最長子數(shù)組的長度怎么算
如上圖所示，綠色區(qū)域是所求的子數(shù)組長度，所以長度計(jì)算就為：i - j
代碼如下：
class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash;hash[0] = -1; //處理特殊情況int sum = 0, ret = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1;//計(jì)算當(dāng)前位置的前綴和，并把0全替換為-1if(hash.count(sum)) ret = max(i - hash[sum], ret);//這里需要加else，為了保證出現(xiàn)重復(fù)的sum，只保留第一次的，確保子數(shù)組長度最長else hash[sum] = i;}return ret;}
};題目八：矩陣區(qū)域和
給你一個(gè)?m x n?的矩陣?mat?和一個(gè)整數(shù)?k?，請你返回一個(gè)矩陣?answer?，其中每個(gè)?answer[i][j]?是所有滿足下述條件的元素?mat[r][c]?的和：?
i - k <= r <= i + k,j - k <= c <= j + k?且(r, c)?在矩陣內(nèi)。
示例 1：
輸入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 輸出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：
輸入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2 輸出：[[45,45,45],[45,45,45],[45,45,45]]
這道題的題意其實(shí)很簡單，就是有一個(gè)m × n的矩陣，再給一個(gè)整數(shù)k，要求每一個(gè)位置都向上下左右擴(kuò)展k個(gè)單位(超出的部分不算)，擴(kuò)展后的區(qū)域的元素之和，就是原位置的元素值，以示例一為例：
2號位置就是計(jì)算紅色區(qū)域的元素和，上面虛線就表示超出的范圍，忽略
5號位置就是計(jì)算藍(lán)色區(qū)域的元素和
這道題就很明顯是要用到二維前綴和了，需要在這里再次提醒，二維前綴和不需要背模版，只需要畫圖理解，很快就能自己現(xiàn)推一個(gè)公式出來，理解最重要！
對于此題來說，給一個(gè)坐標(biāo)(i, j)，那么這個(gè)坐標(biāo)所對應(yīng)需要計(jì)算的區(qū)域就是從(i-k, j-k)到(i+k, j+k)，此時(shí)需要考慮是否會超出矩陣的范圍，所以做如下處理：
x1 = max(0, i-k)，x2 = min(m-1, i+k)
y1 = max(0, j-k)，y2 = min(n-1, j+k)
上述講解是用于求answer矩陣的每個(gè)位置對應(yīng)的(x1,y1)和(x2,y2)坐標(biāo)的，但是有一個(gè)細(xì)節(jié)問題需要注意：
在使用前綴和時(shí)，我們?yōu)榱四軌蛘Ｊ褂?#xff0c;數(shù)組的下標(biāo)都是從1開始的，因?yàn)閺?開始會出現(xiàn)越界訪問的問題，而此題的下標(biāo)是從0開始的，所以需要考慮下標(biāo)的映射關(guān)系
題目中所給的mat矩陣是3×3的，而我們想正常使用前綴和，就得讓坐標(biāo)從1開始，也就是相比于mat矩陣，多加一行多加一列，所以mat和answer就變?yōu)橄聢D所示：
由于dp數(shù)組多了一行一列，所以就會有下面這種情況：
我們想預(yù)處理dp二維數(shù)組中的(x, y)位置時(shí)，需要再mat中找的是(x-1, y-1)位置
并且形成最終的answer數(shù)組的(x, y)位置時(shí)，所需要dp數(shù)組中的位置又是(x+1, y+1)
此時(shí)就有兩種處理思路：
第一種思路：在預(yù)處理dp數(shù)組時(shí)，在原始的公式中把每一個(gè)x1、x2、y1、y2都+1，這樣才能對應(yīng)到mat二維數(shù)組中的元素
但是這樣處理比較麻煩，每一個(gè)位置都需要改
第二種思路：將剛剛計(jì)算的x1、x2、y1、y2是原始mat矩陣的下標(biāo)，如果想在dp矩陣中找位置，每個(gè)后面都+1即可，這樣就完成了上述操作，比較簡便
x1 = max(0, i-k)+1，x2 = min(m-1, i+k)+1
y1 = max(0, j-k)+1，y2 = min(n-1, j+k)+1
代碼如下：
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1));vector<vector<int>> answer(m, vector<int>(n));//預(yù)處理前綴和數(shù)組dpfor(int i = 1; i < m+1; i++)for(int j = 1; j < n+1; j++)dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];//使用前綴和數(shù)組for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int x1 = max(0, i-k) + 1, y1 = max(0, j-k) + 1;int x2 = min(m-1, i+k) + 1, y2 = min(n-1, j+k) + 1;answer[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];}}return answer;}
};前綴和題目到此結(jié)束