題目一：

算法原理：

?這道題是一維前綴和的模板題，通過這道題我們可以了解什么是前綴和

題意很簡單，就是先輸入數(shù)組個數(shù)和查詢次數(shù)，然后將數(shù)組的值放進數(shù)組，每次查詢給2個數(shù)，第一個是起點，第二個是終點，打印這個區(qū)間的和

稍微需要注意的是，這里的數(shù)組存放是從下標1開始的，而不是從下標0開始，至于為什么，等到后面講前綴和的時候就知道了

老規(guī)矩，先用暴力解決，根據(jù)題意，用循環(huán)來累加起點到終點的和，就是將題目的要求轉(zhuǎn)化成代碼，所以很簡單，但是時間復雜度是O（n*q），因為每次查詢都需要遍歷一次數(shù)組，最壞的情況就是q次，每次都從1到n求和，所以是O（n*q）

而題目中數(shù)據(jù)范圍n，q最高來到了10^5，所以O(shè)（n*q）的時間復雜度來到了10^10，一定會超時

接下來就采用前綴和的方法來解決這道題

前綴和分為兩步

第一步：創(chuàng)建前綴和數(shù)組dp（下標中對應的值等于另一個數(shù)組下標前的所有值之和）

第二步：使用前綴和數(shù)組

比如第一步

創(chuàng)建 dp時，就是將原數(shù)組arr進行累加

dp1下標就是arr1下標的和，dp2下標就是arr1下標+2下標的和，dp3下標就是arr1下標+2下標+3下標的和，如此類推

當然到第三個之后就不用傻乎乎的又從頭加到尾，只需要拿dp數(shù)組的前一個值加上當前arr對應的值即可

接下來是第二步

根據(jù)題意，需要我們找到L到r區(qū)間的和，那么我們就可以用r之前的和減去L之前的和，也就是作差值，就能得到L到r的和

而又因為我們已經(jīng)在前綴和數(shù)組中存儲好了r之前的和以及L之前的和，之間拿來用即可，這里的時間復雜度就是O（1）

轉(zhuǎn)化為代碼形式就是dp[r]-dp[l-1]

所以綜上，使用前綴和的算法，就能將時間復雜度降為O（q）+O（n）

其中O（q）是進行q次查詢，每次查詢的時間復雜度都是O（1）

O（n）是在創(chuàng)建前綴和數(shù)組時，遍歷原數(shù)組的值

這也是前綴和數(shù)組解決的問題：用來快速計算一段連續(xù)區(qū)間的和

代碼1：

import java.util.Scanner;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);//輸入n和qint n=in.nextInt();int q=in.nextInt();//創(chuàng)建原數(shù)組，并放進去int[] arr=new int[n+1];for(int i=1;i<=n;i++){arr[i]=in.nextInt();}//創(chuàng)建前綴和數(shù)組，并計算long[] dp=new long[n+1];for(int i=1;i<=n;i++){dp[i]=dp[i-1]+arr[i];}//查詢q次while(q>0){//輸入查詢區(qū)間的l和rint l=in.nextInt();int r=in.nextInt();//使用前綴和數(shù)組System.out.println(dp[r]-dp[l-1]);//次數(shù)-1q--;}}
}

注：其中在創(chuàng)建前綴和數(shù)組的時候，因為原數(shù)組的值最大來到了10^9，所以避免累加的時候溢出，我們選擇用long來防溢出

題目二：

算法原理：

?就是從剛剛存儲一維數(shù)組的之前所有元素的和的前綴和數(shù)組，變?yōu)榱舜鎯ΧS數(shù)組的矩陣和的前綴和數(shù)組

相較一維，二維要更抽象一點，但是只要畫圖，還是很好理解的

仍然是先暴力，也沒有什么難的，就是從x1，y1開始遍歷，直到x2，y2

而最壞的情況下，就是遍歷整個二維數(shù)組，即要遍歷m行，n列，總共q次

所以時間復雜度O（m*n*q）

由數(shù)據(jù)范圍可知，很容易超時

所以要采用二維前綴和

仍然分為兩步

第一步：創(chuàng)建二維前綴和數(shù)組

第二步：使用二維前綴和數(shù)組

先說第一步：

二維前綴和存儲的是以（1，1）為左上角，該位置為右下角的矩陣和，所以畫圖如下

根據(jù)一些簡單的數(shù)學面積計算，很容易得到這個公式

所以在創(chuàng)建二維前綴和的時候，直接用這個公式進行賦值即可

然后第二步：

有了二維前綴和數(shù)組，接下來要解決的就是如何計算（x1，y1）作為左上角，到（x2，y2）作為右下角之間的矩陣和，還是畫圖如下

?

也是根據(jù)簡單的數(shù)學面積計算，就能得到這個公式

所以二維前綴和并不難，運用的知識幾乎就只是小學數(shù)學最多初中數(shù)學的水平難度，只不過就是將這個數(shù)學知識轉(zhuǎn)化為代碼形式而已

代碼1：

import java.util.Scanner;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt(),m=in.nextInt(),q=in.nextInt();int[][] arr=new int[n+1][m+1];long[][] dp=new long[n+1][m+1];//將數(shù)據(jù)放進數(shù)組for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){arr[i][j]=in.nextInt();}}//創(chuàng)建二維前綴和數(shù)組for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//公式dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+arr[i][j];}}//查詢q次while(q>0){int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();//公式System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);q--;}}
}

注：也是在創(chuàng)建二維前綴和數(shù)組的時候，由于原數(shù)組的值比較大，有可能累加求和的過程中溢出，所以用long來防溢出

題目三：

算法原理：

?先用暴力，遍歷整個數(shù)組，每遍歷到一個下標，就循環(huán)求前面的和以及后面的和，如果相等，則找到了中心下標，返回該下標即可，時間復雜度為O（N^2）

接下來就是優(yōu)化，因為題目中出現(xiàn)連續(xù)區(qū)間求和，所以要聯(lián)想的前綴和的算法

依舊分為兩步，創(chuàng)建前綴和數(shù)組和使用前綴和數(shù)組

第一步：創(chuàng)建前綴和數(shù)組

因為是一維前綴和，所以之間按照模板思路去創(chuàng)建即可，只不過這里下標是從0開始的，所以前綴和的值是不包括當前元素的前面所有元素的和

比如nums=[1,7,3,6,5,6]

創(chuàng)建前綴和數(shù)組就為：

dp=[0,1,8,11,17,22,28]

第二步：使用前綴和數(shù)組

根據(jù)規(guī)律，很容易找到這個公式：

dp[i]==dp[nums.length]-dp[i+1]

轉(zhuǎn)化為人話就是左邊的和等于右邊的和

所以很簡單的就解決了這個題目，時間復雜度為O（2N），也就是O（N）

代碼1：

class Solution {public int pivotIndex(int[] nums) {int n=nums.length;//不管會不會溢出，用long保險long[] dp=new long[n+1];//創(chuàng)建前綴和數(shù)組for(int i=1;i<=n;i++){dp[i]=dp[i-1]+nums[i-1];}//使用前綴和數(shù)組for(int i=0;i<n;i++){if(dp[i]==dp[n]-dp[i+1]){return i;}}//沒找到return -1;}
}

然后這里還可以采用前綴和以及后綴和兩個數(shù)組來解決， 這也是一種前綴和算法，因為本質(zhì)都是預處理，什么是后綴和，很簡單，就是從后往前記錄后面的和，比如i位置，前綴和是存i之前所有元素的和，那么后綴和就是存i之后所有元素的和

其實跟我們上面那個解法唯一的區(qū)別就是，在dp[i]==dp[nums.length]-dp[i+1]這個公式中，我們用dp[nums.length]-dp[i+1]代表了后綴和，所以我們可以用后綴和數(shù)組來記錄這里的值

通過畫圖，很容易找到這個公式

而且這里就沒有必要創(chuàng)建n+1長度的前綴數(shù)組和后綴數(shù)組了，因為當i==n-1時，前綴和里面就已經(jīng)不包括i這個位置的數(shù)了，沒必要

接下來就是使用前綴和數(shù)組和后綴和數(shù)組

那就是遍歷整個數(shù)組，如果該位置的前綴和等于后綴和，那么就返回該位置

?代碼2：

class Solution {public int pivotIndex(int[] nums) {int n=nums.length;//創(chuàng)建前綴和數(shù)組dp1和后綴和數(shù)組dp2long[] dp1=new long[n];long[] dp2=new long[n];//構(gòu)建前綴和數(shù)組for(int i=1;i<n;i++){dp1[i]=dp1[i-1]+nums[i-1];}//構(gòu)建后綴和數(shù)組for(int i=n-2;i>=0;i--){dp2[i]=dp2[i+1]+nums[i+1];}//使用前綴和數(shù)組和后綴和數(shù)組for(int i=0;i<n;i++){if(dp1[i]==dp2[i]){return i;}}//沒找到return -1;}
}

題目四：

算法原理：

?題意很簡單，就是返回除該位置的值的其他元素的乘積，并用數(shù)組保存

第一反應先用暴力，那就是遍歷整個數(shù)組，除了等于該位置時，其他全部都乘一下，保存到數(shù)組里，時間復雜度為O（N^2），不滿足題目要求的O（N）

這里題目也很明確提示了用前綴和算法，其中后綴就是從后往前記錄，本質(zhì)與前綴一樣的

只不過這道題是用乘法，也就是說應該叫做前綴積，后綴積

那么每遍歷到一個數(shù)，只需要用該位置的前綴積*后綴積即可

那么現(xiàn)在就是來到第一步：創(chuàng)建前綴后綴數(shù)組

之前前綴和數(shù)組，我們都默認讓0下標為0，因為是求和，所以不希望干擾其他元素之和，所以用0，而這道題是求積，所以應該讓0下標為1，這樣1*任何數(shù)還是任何數(shù)，所以這里稍微要轉(zhuǎn)換一下思路

這里前綴積長度只用設(shè)置跟原數(shù)組長度一樣即可，因為跟上道題一樣，因為到第一個元素/最后一個元素，前綴積/后綴積本來就不包括這個元素，沒必要

還是通過畫圖，很容易得到這兩個公式

幾乎和上道題的第二種解法一模一樣的，就是加換成了乘

?然后就是使用前綴積數(shù)組和后綴積數(shù)組，遍歷整個數(shù)組，只需讓該位置的前綴積乘后綴積，讓這個值保存到要返回的數(shù)組里即可 nn

代碼1：

class Solution {public int[] productExceptSelf(int[] nums) {int n=nums.length;//創(chuàng)建前綴積數(shù)組dp1和后綴積數(shù)組dp2int[] dp1=new int[n];int[] dp2=new int[n];//這里需要稍微修改一下dp1[0]=dp2[n-1]=1;//構(gòu)建前綴積數(shù)組for(int i=1;i<n;i++){dp1[i]=dp1[i-1]*nums[i-1];}//構(gòu)建后綴積數(shù)組for(int i=n-2;i>=0;i--){dp2[i]=dp2[i+1]*nums[i+1];}//要返回的數(shù)組int[] ret=new int[n];//使用前綴積數(shù)組和后綴積數(shù)組for(int i=0;i<n;i++){ret[i]=dp1[i]*dp2[i];}return ret;}
}

注：題目注明了積不會超過32位整數(shù)，也就是int的范圍，所以用int即可

也許你有一點疑問，上一道題可以只用前綴和就能解決，這道題能不能也只用前綴積解決呢，其實不太可以，雖然我們把上道題的減換成除，即dp[i]==dp[nums.length]/dp[i+1]，首先是題目要求了不能使用除法，雖然投機取巧說我學過>>表示除法，但是當除數(shù)為0時，也行不通，所以這道題基本不能只用前綴積解決

但是前綴加后綴這個方法也不難，也很好理解，所以不要排斥，多一種方法就越好

題目五：

?算法原理：

題意很簡單，就是找數(shù)組中有多少個和為k的子數(shù)組

先用暴力看看大致流程是怎么個事

第一層循環(huán)遍歷整個數(shù)組，每遍歷到一個位置，就以該位置作為子數(shù)組的起始位置，然后第二層位置從該位置開始，往后遍歷，直到數(shù)組最后一個元素，這樣就枚舉了所有子數(shù)組的情況

用一個變量記錄當前子數(shù)組的和，如果等于返回值就+1

這就是暴力枚舉，時間復雜度為O（N^2），空間復雜度為O（1）

然后就來想優(yōu)化，我們之前做過一道題，也是求和為k的子數(shù)組個數(shù)，在那一道題我們使用的是滑動窗口，這一道題好像跟那道題一模一樣，但其實有一點區(qū)別，那就是之前那道題中數(shù)組的值全是正數(shù)，那么就具有單調(diào)性，而這道題的提示中寫了數(shù)組中的值有正有負，所以就不能保證右邊界往右滑動時是遞增的，左邊界往右滑動時是遞減的，不具有單調(diào)性，所以這道題不能使用滑動窗口

但是看到子數(shù)組之類的，也要反應出來滑動窗口算法，至于能不能用，再分析，不能看到子數(shù)組卻想不到滑動窗口

既然滑動窗口不行，然后就該繼續(xù)思考，這道題又出現(xiàn)求數(shù)組的和，那么就該想到前綴和，至于能不能用，就來分析

如果我們創(chuàng)建了一個前綴和數(shù)組，那么接下來就是遍歷前綴和數(shù)組，如果有等于k的，返回值就+1

但是這樣統(tǒng)計不全，比如示例[1,2,3]，k=3

創(chuàng)建前綴和數(shù)組為[0,1,3,6]

遍歷完前綴和數(shù)組，有一個3，那么就返回1，那么這樣就忽略了6-3=3這個區(qū)間的子數(shù)組，因為我們創(chuàng)建的前綴和數(shù)組是默認以第一個元素作為子數(shù)組起始位置的

那么接下來我們就要思考怎么找到6-3=3這個區(qū)間的子數(shù)組，如果又想到遍歷前綴和數(shù)組，每遍歷一個位置，就將該位置作為前綴和數(shù)組的起始位置，那么就又繞回了暴力解法了，甚至還不如暴力解法，還多了前綴和創(chuàng)建的時間復雜度O（N），變成O（N^2+N）

那么如何不通過遍歷，就能找到子數(shù)組呢，這里我們就要改變一下思路，我們之前都是先把整個前綴和創(chuàng)建出來再分析，現(xiàn)在我們每添加一個前綴和的時候，就來分析

我們每添加到i位置的前綴和sum時，就往前面找，如果前面的前綴和有一個sum-k，那么就說明后面就有一個為k的子數(shù)組，同理，有兩個前綴和為sum-k，那么就說明有兩個為k的子數(shù)組，如上圖

那么怎么保存有多少個前綴和為sum-k的個數(shù)呢，是不是就想到哈希表了，專門用來記錄出現(xiàn)次數(shù)的

所以這道題就是采用前綴和+哈希表來解決

而且這道題其實不能真正創(chuàng)建一個前綴和數(shù)組，因為我們是一個一個來分析的，不需要預處理全部前綴和，所以只需要用一個變量記錄當前前綴和，然后到下一個就更新前綴和

還有，如果整個區(qū)間為k，那么sum-k=0，而此時沒有0對應的次數(shù)，但是這種情況又算作一個，所以這時哈希表應該提前put（0，1）解決這種問題

代碼1：

class Solution {public int subarraySum(int[] nums, int k) {//創(chuàng)建哈希表HashMap<Integer,Integer> map=new HashMap<>();//準備工作map.put(0,1);//sum為記錄當前的前綴和，count為有多少個和為k的子數(shù)組int sum=0,count=0;//遍歷數(shù)組for(int x:nums){//記錄當前前綴和sum+=x;//找前面有多少個前綴和為sum-k的子數(shù)組count+=map.getOrDefault(sum-k,0);//更新該位置的前綴和數(shù)組到哈希表中map.put(sum,map.getOrDefault(sum,0)+1);}//返回個數(shù)return count;}
}

雖然代碼很少，但是挺難想的，需要先找到用前綴和數(shù)組，然后采用一步一步來分析，最后通過哈希表來解決分析中的問題，需要多積累經(jīng)驗

題目六：

算法原理：

這道題是某一屆藍橋杯的原題，所以完全可以自己先模擬競賽完成這道題

第一反應當然是暴力，無論后面想沒想到后面前綴和+哈希表的方法，但是總能通過大部分用例

仍然是兩層循環(huán)來枚舉出所有子數(shù)組的情況，然后繼續(xù)判斷，如果此時的子數(shù)組的和能被k整除，那么就返回值+1

代碼1（暴力）：

class Solution {public int subarraysDivByK(int[] nums, int k) {int count=0;//暴力枚舉所有子數(shù)組for(int i=0;i<nums.length;i++){int sum=0;for(int j=i;j<nums.length;j++){sum+=nums[j];//如果子數(shù)組能被整除if(sum/k==((float)sum)/k){//計數(shù)器加1count++;}}}//返回計數(shù)器return count;}
}

很簡單就完成了這道題，用時幾乎不超過5分鐘

雖然沒能全部通過，但是也能通過大部分的用例（68/76）

而藍橋杯的賽制是過多少案例點就給部分分的，不是全過就給滿分，沒全過就0分的賽制，所以在競賽中完全可以先暴力，后面剩余時間再來想優(yōu)化?

然后就是用前綴和+哈希表來解決這道題，這道題跟上一道幾乎一模一樣，就是一個是和為k，一個是和能被k整除，所以大致步驟和細節(jié)都是一樣的，就不贅述了

但是這里有兩點小細節(jié)是上一道題沒有的

第一點：我們上一道題是找之前前綴和中有多少個為sum[i]-k的個數(shù)，那么這道題我們要找的是前綴和的余數(shù)中有多少個為“什么”的個數(shù)？

這里有個定理叫做同余定理

公式（a-b）/ p = k …… 0? ?==>? a%k=b%k

比如（26-12）/? 7? = 2 …… 0

所以26%7=12%7? =5?

證明過程如上，簡單來說就是我們還知道（a+p*k）%p=a%p這個道理

那么我們將（a-b）/ p=k進行左右移項再加上同余，即可得到a%p=b%p

?所以回到我們題目

此時前綴和為sum，我們假設(shè)有一個區(qū)間為k，那么后面這個區(qū)間（sum-k）如果能被k整除，那么就找到一個

所以用同余定理，即可得到我們要找的是前綴和的余數(shù)中有多少個為sum%k的個數(shù)，就能說明前面有多少個能被k整除的子數(shù)組

?第二點：

java中（負數(shù)%正數(shù)）如何修正的問題，因為這道題也是存在正負數(shù)的，所以sum的值也可能為負數(shù)

比如[-1,2,9]，k=2

按照思路，哈希表應該存有（0，1）

然后往后遍歷，sum%k = -1%2=-1，發(fā)現(xiàn)哈希表沒有-1的鍵，返回值不變

哈希表就加上（-1，1）

然后繼續(xù)遍歷，sum%k = 1%2 = 1，發(fā)現(xiàn)哈希表沒有1的鍵，返回值不變

哈希表就加上（1，1）

到這里發(fā)現(xiàn)不對的地方了吧，明明出現(xiàn)了[2]這個子數(shù)組，但是返回值卻沒有加1

按照圖上所示，我們代值畫圖即可

?在數(shù)學中，-1%2=1，即取模的值都為正數(shù)，而在Java中，-1%2=-1，所以這個是有矛盾的點，因此我們要將Java中取模操作后的值進行負轉(zhuǎn)正，也就是統(tǒng)一返回正數(shù)

那么我們就可以sum%k變?yōu)?#xff08;sum%k+k）%k，因為題目中k是恒大于等于2的，而sum%k一定比

-k大，所以加上k后一定是大于0的，因此再%k，返回的就一定是正數(shù)

接下來就是按照上道題的代碼，進行細節(jié)添加即可

代碼1：

class Solution {public int subarraysDivByK(int[] nums, int k) {//創(chuàng)建哈希表HashMap<Integer,Integer> map=new HashMap<>();//準備工作map.put(0,1);//sum為記錄當前的前綴和，count為有多少個和能被k整除的子數(shù)組int sum=0,count=0;//遍歷數(shù)組for(int i=0;i<nums.length;i++){//記錄當前前綴和sum+=nums[i];//找前面有多少個前綴和為sum%k的子數(shù)組count+=map.getOrDefault((sum%k+k)%k,0);//更新該位置的前綴和的余數(shù)數(shù)組到哈希表中map.put((sum%k+k)%k,map.getOrDefault((sum%k+k)%k,0)+1);}//返回數(shù)目return count;}
}

主要要知道有同余定理，以及數(shù)學中負數(shù)求余的值也為正數(shù)，Java取余統(tǒng)一正負的操作

題目七：

算法原理：

題意很簡單，就是找到最長的連續(xù)子數(shù)組，這個子數(shù)組0和1的數(shù)量相等，?那么怎么判斷0和1是否相等呢，其實可以像題目五求和為k的子數(shù)組的方式來求，比如找到和為長度一半的子數(shù)組，就除2這樣也可以，但是因為是只有01兩種情況，那么如果讓0為-1，那么就變成簡單的和為0的子數(shù)組，這樣就可以找到題目要求的子數(shù)組

然后就是按照和為k的子數(shù)組的流程來解決了，只是那道題是找有多少個，而這道題是求最長的子數(shù)組長度，所以在哈希表中存的就不是個數(shù)了，而應該是下標

然后就是如果出現(xiàn)重復的哈希值，是否要更改？在之前那一道題的時候，因為要求個數(shù)，所以每找到一個就要更新對應的個數(shù)，但是這一道題哈希表對應下標也要更改嗎？這里要好好分析一下，很細節(jié)的問題

?比如遍歷到j(luò)下標時存了當前的sum值，然后遍歷到i下標時，發(fā)現(xiàn)又為sum，那么此時就找到一個子數(shù)組的和為0，即j到i這個子數(shù)組，這時如果更新下標則為i，不更新則為j

?然后如果后面又出現(xiàn)和為sum的子數(shù)組，情況就很明了了，我們要更長的子數(shù)組，那么肯定要j到k這個子數(shù)組，也就是左邊界越靠左越好，所以答案是不更新

還有一個小問題就是初始化，之前那道是初始化解決整個數(shù)組和為k，則sum-k為0，0對應的哈希值則應該為1，代表這種情況有一個符合要求的子數(shù)組

而這里假設(shè)就是[0,1]這個數(shù)組，按理來說遍歷到1這里，此時sum為0，而哈希表里沒有0這個key，則長度應該為下標：1-？，而這個？對應的就應該是0這個key對應的值，很明顯長度是2，所以？應該為-1，所以初始化時應該加入（0，-1）這對哈希

代碼1：

class Solution {public int findMaxLength(int[] nums) {HashMap<Integer,Integer> map=new HashMap<>();int len=0;int sum=0;//初始化map.put(0,-1);//遍歷for(int i=0;i<nums.length;i++){//如果是0就加-1，是1就加1sum+=(nums[i]==0?-1:1);//如果找得到key為sumif(map.containsKey(sum)){//更新答案為更長的，但是不更新哈希表len=Math.max(len,i-map.get(sum));}else{//沒找到，則更新哈希表map.put(sum,i);}}//返回答案return len;}
}

題目八：

算法原理：?

題意不是很好理解，得一點一點看著題目的公式和要求，畫圖來理解才大致知道輸出答案的得到流程

根據(jù)公式一點一點套能得到答案，但是在畫圖上直觀簡單來說，就是擴大k圈后其中所有的和

比如示例1中輸出數(shù)組的第一個12就是像上面這樣得來的，即1+2+4+5（超出邊界的就按0處理）

再來一個，比如第二個21就是像上面這樣得來的，即1+2+3+4+5+6（同樣超出邊界就按0處理）

這些就是k==1即擴大1圈的樣子，同理k==2就擴大兩圈再求里面的和

題目終于理解了，那么接下來就是解決問題

暴力那就是一個一個遍歷加，太笨了，而且時間復雜度很高，因為是二維數(shù)組，所以基本都是以m*n為底的多少次方這種時間復雜度了

也是求和，那么就該想到前綴和，又是二維的，那么就該用二維前綴和

回顧一下二維前綴和

分為兩步：創(chuàng)建前綴和數(shù)組，使用前綴和數(shù)組

創(chuàng)建前綴和數(shù)組，畫圖就完事了，然后公式看圖推

就是這一整塊? ?=? ?上面一大塊? +? ?左邊一大塊??-? 多加了一次的A? +? ?這一次要求和的D

使用前綴和數(shù)組，畫圖就完事了，然后公式看圖推

?得知左上角（x1，y1）和右下角（x2，y2），求這個范圍的矩陣和

就是? ?D? =? 整一大塊? -? 上面一大塊? ?-? ? 左邊一大塊? ?+? ?多減了一次的A

同時注意，我們二維前綴和都是從（1，1）開始，也就是說實際是下面這樣，就可以避免討論邊界情況即上面出現(xiàn)[x1-1]或者[y1-1]等，當x1，y1等于0這一系列的邊界討論，而以（1，1）作為起點就可以不用討論邊界情況，默認空的為0

那么這道題就變得很簡單了，返回的數(shù)組中每一個對應（i，j）值，加或者減k，即可得到左上角（x1，y1）和右下角（x2，y2）

只不過如果越界了，那么就默認以原數(shù)組的邊界作為界

那么這時候你就想說那又要分類討論，又要各種if，else，還是太繞了，有沒有更簡單，更無腦的方法呀?

有的兄弟，有的，我們只需要求左上角時i-k和j-k與0求max即可，同理求右下角時，i+k或j+k與行數(shù)m-1或列數(shù)n-1求min即可，如下圖

最后套用公式即可

大致流程就是如上了?，但是有一個小細節(jié)，那就是原數(shù)組是從（0，0）開始的，與第二題的原數(shù)組從（1，1）開始不一樣，那怎么辦呢

其實我們只需要給他加或者減1即可，即在創(chuàng)建二維前綴和時，加上的那一小塊其實對應原數(shù)組要減1

而在使用二維前綴和時，（x1，y1）（x2，y2）其實等于原數(shù)組加1

?簡單的變化關(guān)系就是

前綴和數(shù)組——>原數(shù)組（要減1）

原數(shù)組——>前綴和數(shù)組（要加1）

原因就是前綴和數(shù)組是從（1，1）開始的，而原數(shù)組是從（0，0）開始的，就導致前綴和數(shù)組比原數(shù)組要多一行，多一列，導致下標也多1

代碼1：

class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {//m是行數(shù)，n是列數(shù)int m=mat.length;int n=mat[0].length;//創(chuàng)建前綴和數(shù)組int[][] dp=new int[m+1][n+1];for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){//前綴和數(shù)組要用原數(shù)組要減1dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];}}//創(chuàng)建要返回的二維數(shù)組int[][] ans=new int[m][n];//使用前綴和數(shù)組for(int i=0;i<m;i++){for(int j=0;j<n;j++){//原數(shù)組變到前綴和數(shù)組要加1int x1=Math.max(0,i-k)+1;int y1=Math.max(0,j-k)+1;int x2=Math.min(m-1,i+k)+1;int y2=Math.min(n-1,j+k)+1;ans[i][j]=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];}}return ans;}
}

綜上，基礎(chǔ)中等的前綴和算法就學完啦，總結(jié)就是看見題目有求和，則要想到前綴和，步驟為兩步：創(chuàng)建和使用，其中公式不要死記硬背，畫圖現(xiàn)場推很快的