前缀和模板算法

一)模板前缀和

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

前缀和:快速的得出数组中某一段连续区间的和

暴力破解的话需要从头到尾的进行遍历，时间复杂度就可以达到O(N)，而前缀和时间复杂度是可以达到O(1)的

第一步:预处理创建出一个前缀和数组dp，这个数组和原始数组规模是同等大小的

dp[i]就表示从[1,i]区间内所有数组的和

1到N区间内的和和1到L-1区间内的和本质上来说是同一类问题，研究问题的时候发现是同一类问题，我们就可以把这同一类问题抽象成状态表示，用动态规划的思想来进行解决

假设dp[3]表示的就是从1位置到3位置的所有元素的和，就是1+4+7=12

所以状态转移方程就是:dp[i]=dp[i-1]+array[i]；

第二步:使用前缀和数组解决问题:

dp[i]=dp[r]-dp[l-1]

细节问题:在题干中下标为什么从1开始进行计数?

因为如果题目中给定的范围是0-2，那么势必会访问到dp[-1]此时dp表就会出现下标越界访问的情况

public class Main {public static void main(String[] args) {
//1.输入数据Scanner scanner = new Scanner(System.in);int n=scanner.nextInt();int count=scanner.nextInt();long[] array=new long[n+1];for(int i=1;i<=n;i++){array[i]=scanner.nextLong();}
//2.预处理一个前缀和数组long[] dp=new long[n+1];for(int i=1;i<=n;i++){dp[i]=array[i]+dp[i-1];}
//3.使用前缀和数组while(count>0){count--;int left=scanner.nextInt();int right=scanner.nextInt();System.out.println(dp[right]-dp[left-1]);}}
}

二)二维前缀和

【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)

一)预处理出来一个前缀和矩阵:这个前缀和矩阵必须和原始矩阵规模大小是一样的

dp[i][j]表示从(1，1)这个位置到(i，j)这段区间内，所围成的矩形的，这段区间内所有元素的和

dp[i][j]=dp[i-1][j]+array[i][j]+dp[i][j-1]-dp[i-1][j-1] 

result=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]

自己画图可以不花正方形，可以直接画数进行分析

import java.util.Scanner;
import java.util.Arrays;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {
//1.先进行处理数据的输入Scanner scanner=new Scanner(System.in);int m=scanner.nextInt();int n=scanner.nextInt();int count=scanner.nextInt();//初始化输入次数long[][] array=new long[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){array[i][j]=scanner.nextInt();}}
//2.创建dp表进行填表,使用前缀和数组
long[][] dp=new long[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j]+array[i][j]+dp[i][j-1]-dp[i-1][j-1];}}
//2.进行返回结果,使用前缀和数组while(count>0){int x1=scanner.nextInt();int y1=scanner.nextInt();int x2=scanner.nextInt();int y2=scanner.nextInt();
long result=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
// System.out.println(Arrays.deepToString(dp));System.out.println(result);count--;
}}
}

三)寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣（Leetcode）

暴力枚举:每一次枚举一个中间下标i的时候，都需要把(0-i-1)之间的数进行相加，还需要把(i，array.length)之间的数进行相加一遍，可见时间复杂度会变得非常的高

 一)定义一个状态表示:

f[i]表示从0号位置到i-1位置，所有元素的和

g[i]表示从i+1号位置到n-1位置，所有元素的和

二)根据状态表示推导状态转移方程

f[i]=f[i-1]+array[i-1]

g[i]=g[i+1]+array[i+1]

三)初始化(防止发生数组越界)

f[0]=0，g[n-1]=0

四)填表顺序:

f表:从左向右

g表:从右向左

class Solution {public int pivotIndex(int[] array) {int n=array.length;int[] f=new int[n];//f[i]表示从0号位置到i位置数组中这段区间内的和int[] g=new int[n];//g[i]表示从i+1号位置到n-1位置数组中这段区间的和//最后只是需要得出f[i]=g[i]即可f[0]=0;//填写到f[0]位置的时候数组就会发生越界g[n-1]=0;//因为填写到n-1位置的时候数组就会发生越界for(int i=1;i<n;i++){//f从前向后进行填表f[i]=f[i-1]+array[i-1];}for(int i=n-2;i>=0;i--){//g从后向前填表g[i]=g[i+1]+array[i+1];}for(int i=0;i<n;i++){if(f[i]==g[i]){return i;}}return -1;}
}

四)除自身以外数组的乘积:

238. 除自身以外数组的乘积 - 力扣（Leetcode）

一)定义一个状态表示:

f[i]表示从0-i-1位置这段区间所有元素的乘积

g[i]表示从i+1位置开始到n-1这段区间内所有元素的乘积

二)根据状态表示推导状态转移方程:

f[i]=f[i-1]*array[i-1](0号位置的元素到i-2位置的元素的乘积再乘上array[i-1]位置的元素即可)

g[i]=g[i+1]*array[i+1](从i+2号位置的元素到n-1号位置的元素的乘积再乘以i+1号位置的元素)

三)进行初始化操作:f[0]=1，g[n-1]=1

四)填表顺序:f表从左向右填，g表从右向左填

class Solution {public int[] productExceptSelf(int[] array) {
//1.创建前缀积以及后缀积数组int[] f=new int[array.length];int[] g=new int[array.length];int[] ret=new int[array.length];f[0]=1;g[array.length-1]=1;
//2.初始化for(int i=1;i<array.length;i++){f[i]=f[i-1]*array[i-1];}for(int i=array.length-2;i>=0;i--){g[i]=g[i+1]*array[i+1];}for(int i=0;i<array.length;i++){ret[i]=f[i]*g[i];}return ret;}
}

五)和为K的子数组

剑指 Offer II 010. 和为 k 的子数组 - 力扣（Leetcode）

是列出连续子数组

1)暴力解法:

1)采取枚举策略，定义两个变量i和j，i每次固定不动，j一直向后走，走一步加array[j]，直到遇到sum和等于k，因为我们可以使用N^2的时间复杂度将所有子数组枚举出来

2)但是此时j应该继续向后走，直到j把整个数组遍历完成，因为有可能会出现j遇到整数又遇到负数的情况，此时应该还是让sum=sum+array[j]，如果sum==k，应该再次让count++)，此时的时间复杂度就是O(N^2)，中心思路是找到以某一个位置为起点的子数组

不能使用双指针优化:必须有单调性

如果left到左箭头之间的和和right到右箭头之间的和是等于0的，因为right指针还是不断地向右进行移动，也就是说双指针会漏掉中间的这种情况

class Solution {public int subarraySum(int[] array, int k) {int count=0;for(int i=0;i<array.length;i++){int sum=0;for(int j=i;j<array.length;j++){sum=sum+array[j];if(sum==k) count++;}}return count;}
}

2)前缀和:快速的求出某一段区间的和

2.1)先找到以i位置为结尾的所有子数组(一定是包含i位置的元素的)，先找到和为K的以i位置为结尾子数组有多少个，然后把所有情况都进行累加起来

2.2)从而就转化成了在[0~i-1]区间内，i前面有多少个前缀和等于sum[i]-k

2.3)找到所有以i为结尾的子数组中，有多少和是等于sum[i]-k的，就相当于是找到从0到i区间内的一个位置，使得[0，j-1]位置的和等于sum[i]-k，那么此时求的不就是前缀和dp[j-1]吗

1)如果真的采用上面的思路进行遍历查找[0-i]区间内有多少前缀和等于sum[i]-K，i下标需要从头到尾进行遍历一遍，每一次遍历i下标的时候，还需要从前缀和数组中从0-i位置进行遍历有看看有多少前缀和等于sum[i]-k的，此时就可以使用哈希表来进行记录0-i-1这段区间内的前缀和，这样绿线的部分直接就可以通过哈希表一次直接遍历出蓝色线的部分也就是直接可以求出有多少前缀和

2)那么最终的时间复杂度就是O(N^2)+K，时间复杂度又会飙升；

3)前缀和+哈希表

class Solution {public int subarraySum(int[] array, int k) {//dp[i]表示从0号位置到i号位置所有元素的和,开始初始化dp数组int[] dp=new int[array.length+1];dp[0]=0;for(int i=1;i<=array.length;i++){dp[i]=dp[i-1]+array[i-1];}System.out.println(Arrays.toString(dp));int count=0;//1.使用前缀和注意下标的映射关系
//2.注意新的dp数组left到right区间内的和有多少等于k是dp[right]-dp[left-1]是[left,right]区间内的和for(int left=1;left<=array.length;left++){for(int right=left;right<=array.length;right++){if(dp[right]-dp[left-1]==k) count++;}}return count;}
}

使用哈希表来进行解决，Hash<Int，Int>key存放的是前缀和，Value存放的是前缀和出现的次数，就不需要每一次从0位置到i-1位置来进行查找前缀和有多少等于sum-k的了，只需要统计前缀和出现的次数即可，如果发现sum[j]=sum[i]-k了，那么从j+1位置到i位置的这段区间内和就等于k

1)前缀和加入哈希表的时机:

第一种方式就是将前缀和全部计算出来，然后把前缀和一股脑地全部加入到哈希表中，然后从0号位置到i号位置一直进行遍历查找前缀和等于sum[i]-k的，这会出现重复的情况，可能会统计到i位置之后的前缀和等于sum[i]-k的值，可能会出现重复，但是我们是来查询i前面的前缀和等于sum[i]-k的；

再进行计算i位置之前，哈希表中只是保存[0，i-1]位置之间的前缀和

2)不用真的创建一个前缀和数组:

只需要使用sum来标记前一个位置的前缀和

3)如果整个前缀和等于K

当进行第一次枚举到i位置的时候，发现从0号位置到i位置数组的和是等于k的，那么此时就需要从[0，-1]区间内找一个前缀和等于0的位置，这显然是不存在的，所以应该提前加入到hash表中，hash<0，1>，就是为了避免这种情况被漏掉，所以先把(0，1)加入到哈希表中

class Solution {public int subarraySum(int[] nums, int k) {HashMap<Integer,Integer> result=new HashMap<>();result.put(0,1);int count=0;int sum=0;for(int i=0;i<nums.length;i++){sum=sum+nums[i];//记录当前位置的前缀和count=count+result.getOrDefault(sum-k,0);result.put(sum,result.getOrDefault(sum,0)+1);}return count;}
}

六)和可被 K 整除的子数组

974. 和可被 K 整除的子数组 - 力扣（Leetcode）

1.暴力破解:找出所有前缀和(left到right区间可以被k整除的和，那么left到right区间内的和就可以被k整除)

class Solution {public int subarraysDivByK(int[] array, int k) {int n=array.length;int[] dp=new int[n+1];dp[0]=0;for(int i=1;i<=array.length;i++){dp[i]=dp[i-1]+array[i-1];}int count=0;for(int left=1;left<=array.length;left++){for(int right=left;right<=array.length;right++){int temp=dp[right]-dp[left-1];if(temp%k==0) count++;}}return count;}
}

2.暴力破解:找到所有的子数组，找出和能被k整除的

class Solution {public int subarraysDivByK(int[] array, int k) {int count=0;for(int i=0;i<array.length;i++){int sum=0;for(int j=i;j<array.length;j++){sum=sum+array[j];if(sum%k==0) count++;}}return count;}
}

3.前缀和:

1)同余定理:

1)sum[i]是从0号位置开始到i号位置开始所有元素的和，正好找到j位置使(sum[i]-x)%k==0

(sum[i]-x)/k=t.......0

2)所以说这个题就转化成了从0到i-1区间内，找到有多少个前缀和的余数等于sum%k

(sum%k+k)%k，(哪一个区间i前面的数的所有和%k=sum[i]%k)

3)创建一个哈希表:key是前缀和的余数，value是这个前缀和对应的出现的次数

lass Solution {public int subarraysDivByK(int[] array, int k) {HashMap<Integer,Integer> result=new HashMap<>();result.put(0,1);int count=0;int sum=0;for(int i=0;i<array.length;i++){sum=sum+array[i];count+=result.getOrDefault((sum%k+k)%k,0);result.put((sum%k+k)%k,result.getOrDefault((sum%k+k)%k,0)+1);}return count;   }
}

七)连续数组:

525. 连续数组 - 力扣（Leetcode）

算法原理:

1)将所有的0全部变成-1，然后求整个数组的和是0的最大子数组长度

2)在数组中找出最长的子数组，使子数组中所有元素的和等于0

细节问题:

1)哈希表中存什么？

hash<int,int>key值存放的是前缀和，value值存放的是前缀和所对应的下标

2)什么时候存入到哈希表？

使用完成之后丢入到哈希表

3)如果有重复的sum[i]怎么进行存放呢？

只是保留前面的那一对，i的值越靠近左边越好

4)默认有前缀和等于0的情况，如何进行处理？

hash[0]=-1

5)长度怎么算？

i-j+1-1=i-j

class Solution {public int findMaxLength(int[] array) {for(int i=0;i<array.length;i++){if(array[i]==0) array[i]=-1;}int count=0;int sum=0;HashMap<Integer,Integer> map=new HashMap<>();
//第一个位置存放的是前缀和,第二个位置存放的是下标,最终maxlen里面存放的是长度int maxlen=0;map.put(0,-1);
//如果从0到i位置的元素和已经等于0了,那么此时就是在0到-1区间内寻找和是0的数组,此时长度就是i-0+1,所以要存放0,-1for(int i=0;i<array.length;i++){sum=sum+array[i];if(map.containsKey(sum)){maxlen=Math.max(maxlen,i-map.get(sum));}else{map.put(sum,i);
//如果哈希表中已经存在sum了,就不需要再次进行存放了
//因为我们所需要进行寻找的是长度最大的数组}  }return maxlen;}
}

八)矩阵区域和

1314. 矩阵区域和 - 力扣（Leetcode）

如下图所示，我们要求的中心下标的矩形面积是二维前缀和

(x+k，y+k)所围成的正方形的面积-(x-k，y-k)所围成的正方形的面积

class Solution {public int[][] matrixBlockSum(int[][] array, int k) {int col=array[0].length;int row=array.length;int[][] dp=new int[row+1][col+1];int[][] result=new int[row][col];
//1.初始化二维前缀和,注意下标的映射关系for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+array[i-1][j-1];}}System.out.println(Arrays.deepToString(dp));
//2.计算最终矩阵的值,注意下标的映射关系for(int i=0;i<row;i++){for(int j=0;j<col;j++){int x1=Math.max(i-k,0)+1;int y1=Math.max(j-k,0)+1;int x2=Math.min(i+k,row-1)+1;int y2=Math.min(j+k,col-1)+1;result[i][j]=dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];}}return result;}
}