系统学习算法：专题四 前缀和

题目一：

算法原理：

 这道题是一维前缀和的模板题，通过这道题我们可以了解什么是前缀和

题意很简单，就是先输入数组个数和查询次数，然后将数组的值放进数组，每次查询给2个数，第一个是起点，第二个是终点，打印这个区间的和

稍微需要注意的是，这里的数组存放是从下标1开始的，而不是从下标0开始，至于为什么，等到后面讲前缀和的时候就知道了

老规矩，先用暴力解决，根据题意，用循环来累加起点到终点的和，就是将题目的要求转化成代码，所以很简单，但是时间复杂度是O（n*q），因为每次查询都需要遍历一次数组，最坏的情况就是q次，每次都从1到n求和，所以是O（n*q）

而题目中数据范围n，q最高来到了10^5，所以O（n*q）的时间复杂度来到了10^10，一定会超时

接下来就采用前缀和的方法来解决这道题

前缀和分为两步

第一步：创建前缀和数组dp（下标中对应的值等于另一个数组下标前的所有值之和）

第二步：使用前缀和数组

比如第一步

创建 dp时，就是将原数组arr进行累加

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

当然到第三个之后就不用傻乎乎的又从头加到尾，只需要拿dp数组的前一个值加上当前arr对应的值即可

接下来是第二步

根据题意，需要我们找到L到r区间的和，那么我们就可以用r之前的和减去L之前的和，也就是作差值，就能得到L到r的和

而又因为我们已经在前缀和数组中存储好了r之前的和以及L之前的和，之间拿来用即可，这里的时间复杂度就是O（1）

转化为代码形式就是dp[r]-dp[l-1]

所以综上，使用前缀和的算法，就能将时间复杂度降为O（q）+O（n）

其中O（q）是进行q次查询，每次查询的时间复杂度都是O（1）

O（n）是在创建前缀和数组时，遍历原数组的值

这也是前缀和数组解决的问题：用来快速计算一段连续区间的和

代码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();//创建原数组，并放进去int[] arr=new int[n+1];for(int i=1;i<=n;i++){arr[i]=in.nextInt();}//创建前缀和数组，并计算long[] dp=new long[n+1];for(int i=1;i<=n;i++){dp[i]=dp[i-1]+arr[i];}//查询q次while(q>0){//输入查询区间的l和rint l=in.nextInt();int r=in.nextInt();//使用前缀和数组System.out.println(dp[r]-dp[l-1]);//次数-1q--;}}
}

注：其中在创建前缀和数组的时候，因为原数组的值最大来到了10^9，所以避免累加的时候溢出，我们选择用long来防溢出

题目二：

算法原理：

 就是从刚刚存储一维数组的之前所有元素的和的前缀和数组，变为了存储二维数组的矩阵和的前缀和数组

相较一维，二维要更抽象一点，但是只要画图，还是很好理解的

仍然是先暴力，也没有什么难的，就是从x1，y1开始遍历，直到x2，y2

而最坏的情况下，就是遍历整个二维数组，即要遍历m行，n列，总共q次

所以时间复杂度O（m*n*q）

由数据范围可知，很容易超时

所以要采用二维前缀和

仍然分为两步

第一步：创建二维前缀和数组

第二步：使用二维前缀和数组

先说第一步：

二维前缀和存储的是以（1，1）为左上角，该位置为右下角的矩阵和，所以画图如下

根据一些简单的数学面积计算，很容易得到这个公式

所以在创建二维前缀和的时候，直接用这个公式进行赋值即可

然后第二步：

有了二维前缀和数组，接下来要解决的就是如何计算（x1，y1）作为左上角，到（x2，y2）作为右下角之间的矩阵和，还是画图如下

 

也是根据简单的数学面积计算，就能得到这个公式

所以二维前缀和并不难，运用的知识几乎就只是小学数学最多初中数学的水平难度，只不过就是将这个数学知识转化为代码形式而已

代码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];//将数据放进数组for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){arr[i][j]=in.nextInt();}}//创建二维前缀和数组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--;}}
}

注：也是在创建二维前缀和数组的时候，由于原数组的值比较大，有可能累加求和的过程中溢出，所以用long来防溢出

题目三：

算法原理：

 先用暴力，遍历整个数组，每遍历到一个下标，就循环求前面的和以及后面的和，如果相等，则找到了中心下标，返回该下标即可，时间复杂度为O（N^2）

接下来就是优化，因为题目中出现连续区间求和，所以要联想的前缀和的算法

依旧分为两步，创建前缀和数组和使用前缀和数组

第一步：创建前缀和数组

因为是一维前缀和，所以之间按照模板思路去创建即可，只不过这里下标是从0开始的，所以前缀和的值是不包括当前元素的前面所有元素的和

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

创建前缀和数组就为：

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

第二步：使用前缀和数组

根据规律，很容易找到这个公式：

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

转化为人话就是左边的和等于右边的和

所以很简单的就解决了这个题目，时间复杂度为O（2N），也就是O（N）

代码1：

class Solution {public int pivotIndex(int[] nums) {int n=nums.length;//不管会不会溢出，用long保险long[] dp=new long[n+1];//创建前缀和数组for(int i=1;i<=n;i++){dp[i]=dp[i-1]+nums[i-1];}//使用前缀和数组for(int i=0;i<n;i++){if(dp[i]==dp[n]-dp[i+1]){return i;}}//没找到return -1;}
}

然后这里还可以采用前缀和以及后缀和两个数组来解决， 这也是一种前缀和算法，因为本质都是预处理，什么是后缀和，很简单，就是从后往前记录后面的和，比如i位置，前缀和是存i之前所有元素的和，那么后缀和就是存i之后所有元素的和

其实跟我们上面那个解法唯一的区别就是，在dp[i]==dp[nums.length]-dp[i+1]这个公式中，我们用dp[nums.length]-dp[i+1]代表了后缀和，所以我们可以用后缀和数组来记录这里的值

通过画图，很容易找到这个公式

而且这里就没有必要创建n+1长度的前缀数组和后缀数组了，因为当i==n-1时，前缀和里面就已经不包括i这个位置的数了，没必要

接下来就是使用前缀和数组和后缀和数组

那就是遍历整个数组，如果该位置的前缀和等于后缀和，那么就返回该位置

 代码2：

class Solution {public int pivotIndex(int[] nums) {int n=nums.length;//创建前缀和数组dp1和后缀和数组dp2long[] dp1=new long[n];long[] dp2=new long[n];//构建前缀和数组for(int i=1;i<n;i++){dp1[i]=dp1[i-1]+nums[i-1];}//构建后缀和数组for(int i=n-2;i>=0;i--){dp2[i]=dp2[i+1]+nums[i+1];}//使用前缀和数组和后缀和数组for(int i=0;i<n;i++){if(dp1[i]==dp2[i]){return i;}}//没找到return -1;}
}

题目四：

算法原理：

 题意很简单，就是返回除该位置的值的其他元素的乘积，并用数组保存

第一反应先用暴力，那就是遍历整个数组，除了等于该位置时，其他全部都乘一下，保存到数组里，时间复杂度为O（N^2），不满足题目要求的O（N）

这里题目也很明确提示了用前缀和算法，其中后缀就是从后往前记录，本质与前缀一样的

只不过这道题是用乘法，也就是说应该叫做前缀积，后缀积

那么每遍历到一个数，只需要用该位置的前缀积*后缀积即可

那么现在就是来到第一步：创建前缀后缀数组

之前前缀和数组，我们都默认让0下标为0，因为是求和，所以不希望干扰其他元素之和，所以用0，而这道题是求积，所以应该让0下标为1，这样1*任何数还是任何数，所以这里稍微要转换一下思路

这里前缀积长度只用设置跟原数组长度一样即可，因为跟上道题一样，因为到第一个元素/最后一个元素，前缀积/后缀积本来就不包括这个元素，没必要

还是通过画图，很容易得到这两个公式

几乎和上道题的第二种解法一模一样的，就是加换成了乘

 然后就是使用前缀积数组和后缀积数组，遍历整个数组，只需让该位置的前缀积乘后缀积，让这个值保存到要返回的数组里即可 nn

代码1：

class Solution {public int[] productExceptSelf(int[] nums) {int n=nums.length;//创建前缀积数组dp1和后缀积数组dp2int[] dp1=new int[n];int[] dp2=new int[n];//这里需要稍微修改一下dp1[0]=dp2[n-1]=1;//构建前缀积数组for(int i=1;i<n;i++){dp1[i]=dp1[i-1]*nums[i-1];}//构建后缀积数组for(int i=n-2;i>=0;i--){dp2[i]=dp2[i+1]*nums[i+1];}//要返回的数组int[] ret=new int[n];//使用前缀积数组和后缀积数组for(int i=0;i<n;i++){ret[i]=dp1[i]*dp2[i];}return ret;}
}

注：题目注明了积不会超过32位整数，也就是int的范围，所以用int即可

也许你有一点疑问，上一道题可以只用前缀和就能解决，这道题能不能也只用前缀积解决呢，其实不太可以，虽然我们把上道题的减换成除，即dp[i]==dp[nums.length]/dp[i+1]，首先是题目要求了不能使用除法，虽然投机取巧说我学过>>表示除法，但是当除数为0时，也行不通，所以这道题基本不能只用前缀积解决

但是前缀加后缀这个方法也不难，也很好理解，所以不要排斥，多一种方法就越好

题目五：

 算法原理：

题意很简单，就是找数组中有多少个和为k的子数组

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

第一层循环遍历整个数组，每遍历到一个位置，就以该位置作为子数组的起始位置，然后第二层位置从该位置开始，往后遍历，直到数组最后一个元素，这样就枚举了所有子数组的情况

用一个变量记录当前子数组的和，如果等于返回值就+1

这就是暴力枚举，时间复杂度为O（N^2），空间复杂度为O（1）

然后就来想优化，我们之前做过一道题，也是求和为k的子数组个数，在那一道题我们使用的是滑动窗口，这一道题好像跟那道题一模一样，但其实有一点区别，那就是之前那道题中数组的值全是正数，那么就具有单调性，而这道题的提示中写了数组中的值有正有负，所以就不能保证右边界往右滑动时是递增的，左边界往右滑动时是递减的，不具有单调性，所以这道题不能使用滑动窗口

但是看到子数组之类的，也要反应出来滑动窗口算法，至于能不能用，再分析，不能看到子数组却想不到滑动窗口

既然滑动窗口不行，然后就该继续思考，这道题又出现求数组的和，那么就该想到前缀和，至于能不能用，就来分析

如果我们创建了一个前缀和数组，那么接下来就是遍历前缀和数组，如果有等于k的，返回值就+1

但是这样统计不全，比如示例[1,2,3]，k=3

创建前缀和数组为[0,1,3,6]

遍历完前缀和数组，有一个3，那么就返回1，那么这样就忽略了6-3=3这个区间的子数组，因为我们创建的前缀和数组是默认以第一个元素作为子数组起始位置的

那么接下来我们就要思考怎么找到6-3=3这个区间的子数组，如果又想到遍历前缀和数组，每遍历一个位置，就将该位置作为前缀和数组的起始位置，那么就又绕回了暴力解法了，甚至还不如暴力解法，还多了前缀和创建的时间复杂度O（N），变成O（N^2+N）

那么如何不通过遍历，就能找到子数组呢，这里我们就要改变一下思路，我们之前都是先把整个前缀和创建出来再分析，现在我们每添加一个前缀和的时候，就来分析

我们每添加到i位置的前缀和sum时，就往前面找，如果前面的前缀和有一个sum-k，那么就说明后面就有一个为k的子数组，同理，有两个前缀和为sum-k，那么就说明有两个为k的子数组，如上图

那么怎么保存有多少个前缀和为sum-k的个数呢，是不是就想到哈希表了，专门用来记录出现次数的

所以这道题就是采用前缀和+哈希表来解决

而且这道题其实不能真正创建一个前缀和数组，因为我们是一个一个来分析的，不需要预处理全部前缀和，所以只需要用一个变量记录当前前缀和，然后到下一个就更新前缀和

还有，如果整个区间为k，那么sum-k=0，而此时没有0对应的次数，但是这种情况又算作一个，所以这时哈希表应该提前put（0，1）解决这种问题

代码1：

class Solution {public int subarraySum(int[] nums, int k) {//创建哈希表HashMap<Integer,Integer> map=new HashMap<>();//准备工作map.put(0,1);//sum为记录当前的前缀和，count为有多少个和为k的子数组int sum=0,count=0;//遍历数组for(int x:nums){//记录当前前缀和sum+=x;//找前面有多少个前缀和为sum-k的子数组count+=map.getOrDefault(sum-k,0);//更新该位置的前缀和数组到哈希表中map.put(sum,map.getOrDefault(sum,0)+1);}//返回个数return count;}
}

虽然代码很少，但是挺难想的，需要先找到用前缀和数组，然后采用一步一步来分析，最后通过哈希表来解决分析中的问题，需要多积累经验

题目六：

算法原理：

这道题是某一届蓝桥杯的原题，所以完全可以自己先模拟竞赛完成这道题

第一反应当然是暴力，无论后面想没想到后面前缀和+哈希表的方法，但是总能通过大部分用例

仍然是两层循环来枚举出所有子数组的情况，然后继续判断，如果此时的子数组的和能被k整除，那么就返回值+1

代码1（暴力）：

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

很简单就完成了这道题，用时几乎不超过5分钟

虽然没能全部通过，但是也能通过大部分的用例（68/76）

而蓝桥杯的赛制是过多少案例点就给部分分的，不是全过就给满分，没全过就0分的赛制，所以在竞赛中完全可以先暴力，后面剩余时间再来想优化 

然后就是用前缀和+哈希表来解决这道题，这道题跟上一道几乎一模一样，就是一个是和为k，一个是和能被k整除，所以大致步骤和细节都是一样的，就不赘述了

但是这里有两点小细节是上一道题没有的

第一点：我们上一道题是找之前前缀和中有多少个为sum[i]-k的个数，那么这道题我们要找的是前缀和的余数中有多少个为“什么”的个数？

这里有个定理叫做同余定理

公式（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，我们假设有一个区间为k，那么后面这个区间（sum-k）如果能被k整除，那么就找到一个

所以用同余定理，即可得到我们要找的是前缀和的余数中有多少个为sum%k的个数，就能说明前面有多少个能被k整除的子数组

 第二点：

java中（负数%正数）如何修正的问题，因为这道题也是存在正负数的，所以sum的值也可能为负数

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

按照思路，哈希表应该存有（0，1）

然后往后遍历，sum%k = -1%2=-1，发现哈希表没有-1的键，返回值不变

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

然后继续遍历，sum%k = 1%2 = 1，发现哈希表没有1的键，返回值不变

哈希表就加上（1，1）

到这里发现不对的地方了吧，明明出现了[2]这个子数组，但是返回值却没有加1

按照图上所示，我们代值画图即可

 在数学中，-1%2=1，即取模的值都为正数，而在Java中，-1%2=-1，所以这个是有矛盾的点，因此我们要将Java中取模操作后的值进行负转正，也就是统一返回正数

那么我们就可以sum%k变为（sum%k+k）%k，因为题目中k是恒大于等于2的，而sum%k一定比

-k大，所以加上k后一定是大于0的，因此再%k，返回的就一定是正数

接下来就是按照上道题的代码，进行细节添加即可

代码1：

class Solution {public int subarraysDivByK(int[] nums, int k) {//创建哈希表HashMap<Integer,Integer> map=new HashMap<>();//准备工作map.put(0,1);//sum为记录当前的前缀和，count为有多少个和能被k整除的子数组int sum=0,count=0;//遍历数组for(int i=0;i<nums.length;i++){//记录当前前缀和sum+=nums[i];//找前面有多少个前缀和为sum%k的子数组count+=map.getOrDefault((sum%k+k)%k,0);//更新该位置的前缀和的余数数组到哈希表中map.put((sum%k+k)%k,map.getOrDefault((sum%k+k)%k,0)+1);}//返回数目return count;}
}

主要要知道有同余定理，以及数学中负数求余的值也为正数，Java取余统一正负的操作

题目七：

算法原理：

题意很简单，就是找到最长的连续子数组，这个子数组0和1的数量相等， 那么怎么判断0和1是否相等呢，其实可以像题目五求和为k的子数组的方式来求，比如找到和为长度一半的子数组，就除2这样也可以，但是因为是只有01两种情况，那么如果让0为-1，那么就变成简单的和为0的子数组，这样就可以找到题目要求的子数组

然后就是按照和为k的子数组的流程来解决了，只是那道题是找有多少个，而这道题是求最长的子数组长度，所以在哈希表中存的就不是个数了，而应该是下标

然后就是如果出现重复的哈希值，是否要更改？在之前那一道题的时候，因为要求个数，所以每找到一个就要更新对应的个数，但是这一道题哈希表对应下标也要更改吗？这里要好好分析一下，很细节的问题

 比如遍历到j下标时存了当前的sum值，然后遍历到i下标时，发现又为sum，那么此时就找到一个子数组的和为0，即j到i这个子数组，这时如果更新下标则为i，不更新则为j

 然后如果后面又出现和为sum的子数组，情况就很明了了，我们要更长的子数组，那么肯定要j到k这个子数组，也就是左边界越靠左越好，所以答案是不更新

还有一个小问题就是初始化，之前那道是初始化解决整个数组和为k，则sum-k为0，0对应的哈希值则应该为1，代表这种情况有一个符合要求的子数组

而这里假设就是[0,1]这个数组，按理来说遍历到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;}
}

题目八：

算法原理： 

题意不是很好理解，得一点一点看着题目的公式和要求，画图来理解才大致知道输出答案的得到流程

根据公式一点一点套能得到答案，但是在画图上直观简单来说，就是扩大k圈后其中所有的和

比如示例1中输出数组的第一个12就是像上面这样得来的，即1+2+4+5（超出边界的就按0处理）

再来一个，比如第二个21就是像上面这样得来的，即1+2+3+4+5+6（同样超出边界就按0处理）

这些就是k==1即扩大1圈的样子，同理k==2就扩大两圈再求里面的和

题目终于理解了，那么接下来就是解决问题

暴力那就是一个一个遍历加，太笨了，而且时间复杂度很高，因为是二维数组，所以基本都是以m*n为底的多少次方这种时间复杂度了

也是求和，那么就该想到前缀和，又是二维的，那么就该用二维前缀和

回顾一下二维前缀和

分为两步：创建前缀和数组，使用前缀和数组

创建前缀和数组，画图就完事了，然后公式看图推

就是这一整块   =   上面一大块  +   左边一大块  -  多加了一次的A  +   这一次要求和的D

使用前缀和数组，画图就完事了，然后公式看图推

 得知左上角（x1，y1）和右下角（x2，y2），求这个范围的矩阵和

就是   D  =  整一大块  -  上面一大块   -    左边一大块   +   多减了一次的A

同时注意，我们二维前缀和都是从（1，1）开始，也就是说实际是下面这样，就可以避免讨论边界情况即上面出现[x1-1]或者[y1-1]等，当x1，y1等于0这一系列的边界讨论，而以（1，1）作为起点就可以不用讨论边界情况，默认空的为0

那么这道题就变得很简单了，返回的数组中每一个对应（i，j）值，加或者减k，即可得到左上角（x1，y1）和右下角（x2，y2）

只不过如果越界了，那么就默认以原数组的边界作为界

那么这时候你就想说那又要分类讨论，又要各种if，else，还是太绕了，有没有更简单，更无脑的方法呀 

有的兄弟，有的，我们只需要求左上角时i-k和j-k与0求max即可，同理求右下角时，i+k或j+k与行数m-1或列数n-1求min即可，如下图

最后套用公式即可

大致流程就是如上了 ，但是有一个小细节，那就是原数组是从（0，0）开始的，与第二题的原数组从（1，1）开始不一样，那怎么办呢

其实我们只需要给他加或者减1即可，即在创建二维前缀和时，加上的那一小块其实对应原数组要减1

而在使用二维前缀和时，（x1，y1）（x2，y2）其实等于原数组加1

 简单的变化关系就是

前缀和数组——>原数组（要减1）

原数组——>前缀和数组（要加1）

原因就是前缀和数组是从（1，1）开始的，而原数组是从（0，0）开始的，就导致前缀和数组比原数组要多一行，多一列，导致下标也多1

代码1：

class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {//m是行数，n是列数int m=mat.length;int n=mat[0].length;//创建前缀和数组int[][] dp=new int[m+1][n+1];for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){//前缀和数组要用原数组要减1dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];}}//创建要返回的二维数组int[][] ans=new int[m][n];//使用前缀和数组for(int i=0;i<m;i++){for(int j=0;j<n;j++){//原数组变到前缀和数组要加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;}
}

综上，基础中等的前缀和算法就学完啦，总结就是看见题目有求和，则要想到前缀和，步骤为两步：创建和使用，其中公式不要死记硬背，画图现场推很快的