前言
在求数组或者矩阵求和等问题,我们如果采用暴力解法,时间复杂度可能会达到O(n)或者更高,因此,我们可利用前缀和来解决。
前缀和
前缀和是指序列中的n项和,相当于数学问题中秋数列的前n项和。主要用于数组或列表中求解子数组的和、查询区间和等问题,能够将时间复杂度从O(n)降低到O(1)。
接下来我们就通过题目来更好的来理解前缀和。
【模板】前缀和
算法分析
本道题就是在长度为n的数组中根据输入的区间下标[L,R]来计算区间和。如果我们使用暴力解法,时间复杂度为O(n),但是我们有更优的解法,使用前缀和,能使查询区间和的复杂度降为O(1).
算法步骤
- 初始化:根据题目需求,定义变量n,q,l,r,并等待输入。定义数组a长度为(n+1),同理,这里需要借助一个前缀和数组dp,长度也为(n+1);
- 预处理:给n,q,数组元素,l,r赋值之后,就可以进行下步操作。
- 处理前缀和数组:前缀和数组顾名思义就是用来计算前缀和的大小,(前缀和数组中dp[i]指的是包括i在内之前的元素之和),如果我们每次计算dp[i]都要遍历到i,时间复杂度为O(N^2),但我们可以知道的是,每次计算前缀和,都是dp[i-1]+a[i](即i之前的前缀和+a[i]).所以我们计算前缀和dp[i]=dp[i-1]+a[i]
- 计算区间和:当我们处理完前缀和数组之后,计算[L,R] 的区间和,我们可以理解为计算(R)之前的和减去(L-1)之前的和,即sum=dp[r]-dp[l-1]。
- 处理边界:我们这里计算前缀和时,数组下标应该从1开始,若从0开始,当计算前缀和数组dp[0]=dp[-1]+a[0],就会越界,因此下标应该从1开始。且a[0]=dp[0]=0.
- 变量类型:通过题目要求,0<=a[i]<=10^9,因此我们不能使用int类型,而是使用long。
算法代码
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();int q = in.nextInt();long[] a = new long[n + 1];long[] dp = new long[n + 1];a[0] = dp[0] = 0;for (int i = 1; i <= n; i++) {a[i] = in.nextLong();}//处理前缀和数组for (int i = 1; i <= n; i++) {dp[i] = dp[i - 1] + a[i];}//计算区间和while (q > 0) {int l = in.nextInt();int r = in.nextInt();long sum = dp[r] - dp[l - 1];System.out.println(sum);q--;}}
}
时间复杂度为O(n+q),n是数组长度,q是查询次数。
空间复杂度为为O(n),需要借助dp数组。
算法示例
以
8 1
3 4 5 8 2 3 4 5
4 7为例
第一步:初始化 、并预处理a数组
根据输入的值:n=8,q=1 a[9]={0,3,4,5,8,2,3,4,5}
第二步:处理前缀和数组
dp[9]={0,3,7,12,20,22,25,29,35}
第三步:根据L和R计算前缀和
在输入中,我们可以得到L=4,R=7
所以前缀和sum=dp[7]-d[3]=29-12=17
我们可以测试一下,可以看到,结果确实与我们算的一致。
【模板】
根据这道题目,我们可以总结出计算前缀和时的模板:
【模板】二维前缀和
算法分析
本道题是要在一个矩阵中求子矩阵的和,如果我们使用暴力解法,时间复杂度为O(n*m*q),会超时,但对于这种求子矩阵和的问题,我们可以使用前缀和来解决。
在说算法步骤之前,先来补充个知识,我们在计算一个矩阵的大小时,其实是可以将分为几部分来求解的,对于本道题的矩阵,我们可以分解为:
算法步骤
- 初始化:定义n和m,并创建(n+1)*(m+1)的二维数组a和(n+1)*(m+1)的二维前缀和数组dp。这里是为了防止溢出。同时也需要创建一个(n+1)*(m+1)的前缀和矩阵。
- 矩阵处理:在上面的图片中,我们知道了一个矩阵可以切块计算。那么我们在计算dp[i][j]的时候,其实也是可以分成4部分。我们在计算A部分的时候,是很容易计算的(其实就是dp[i-1][j-1]的和),但我们想要知道B、C部分的和,那是有点困难的,但我们可以看出,如果我们把A和B、A和C结合来,其实就是前缀和dp[i-1][j]和dp[i][j-1],这从我们前缀和数组中是可以知道的。所以,我们在处理前缀和矩阵的时候,可以根据公式:
dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1]
即S=(A+B)+(A+C)+D-A
3.计算子矩阵和:当我们处理完前缀和矩阵之后,就可以利用矩阵来进行求和。
根据所给的坐标(X1,Y1),(X2,Y2),我们可以得到以下:
同理的,我们根据坐标,将矩阵分为4部分,其中D矩阵就是我们所要求的子矩阵。我们想要求D的话,根据
D=(A+B+C+D)-(A+B)-(A+C)+A
=dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
即可得到。
算法代码
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int q=sc.nextInt();long[][] a=new long[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++){a[i][j]=sc.nextLong();}}//预处理矩阵for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//S=(A+B)+(A+C)+D-Adp[i][j]=dp[i-1][j]+dp[i][j-1]+a[i][j]-dp[i-1][j-1];}}//求子矩阵和while(q>0){int x1=sc.nextInt();int y1=sc.nextInt();int x2=sc.nextInt();int y2=sc.nextInt();//sum=(A+B+C+D)-(A+B)-(A+C)+A=Dlong sum=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];System.out.println(sum);q--;}}
}
时间复杂度为O(n*m)+O(q),n,m为二维数组的行,列,q为查询次数。
空间复杂度为O(n*m).需要开辟两个数组,a和dp。
算法示例
以
3 4 3 1 2 3 4 3 2 1 0 1 5 7 8 1 1 2 2为例
第一步:初始化
根据输入的值,可以得到:
n=3,m=4,q=3
a数组如下
第二步:处理前缀和矩阵
根据二维数组a,我们可以计算出前缀和数组dp为
【模板】
寻找数组的中心下标
算法分析
这道题是要我们在数组中,找以一个点为中心,左右区间和相等。这里我们可以利用前缀和来进行解答。这里我们需要利用到两个数组,yp和np。
算法步骤
- 初始化:定义n,并初始化为nums.length.定义两个二维数组yp(前缀合)和np(后缀和)并设置长度为n;yp用来存储从前往后的和,np用来存储从后往前的和。
- 预处理yp和np:yp从1开始往后遍历,yp=yp[i-1]+nums[i-1],循环条件为:i<n;np从nums.length-2开始,np[i]=np[i+1]+nums[i+1],循环条件为:i>=0.
- 判断:当处理完yp和np之后,我们就可判断yp和np中数组元素是否相等,若相等,证明以该点为中心点的左右区间和相等,返回此时的下标即可。当遍历完数组,若没有相等的,则返回-1.
算法代码
/*** 寻找数组的中心索引* 中心索引的左侧元素之和等于右侧元素之和* * @param nums 输入的整数数组* @return 返回中心索引,如果不存在,则返回-1*/public int pivotIndex(int[] nums) {// 数组长度int n=nums.length;// yp数组用于存储从左侧累加的元素之和int[] yp=new int[n];// np数组用于存储从右侧累加的元素之和int[] np=new int[n];// 从左侧开始累加,计算每个位置左侧元素之和for(int i=1;i<n;i++){yp[i]=yp[i-1]+nums[i-1];}// 从右侧开始累加,计算每个位置右侧元素之和for(int i=n-2;i>=0;i--){np[i]=np[i+1]+nums[i+1];}// 遍历数组,寻找中心索引for(int i=0;i<n;i++){// 当找到左右两侧元素之和相等的位置时,返回该索引if(yp[i]==np[i]){return i;}}// 如果没有找到中心索引,返回-1return -1;}
算法示例:
以nums = [1, 7, 3, 6, 5, 6]为例
第一步:初始化
n=6
第二步:预处理
yp={0,1,8,11,16,21}
np={27,20,17,11,6,0}
第三步:判断
我们可以看到,yp[3]=np[3]=11,此时返回下标3即可。
除自身以外数组的乘积
算法分析
本道题与上一道题类似,不过这道题是为了求除当前下标的数,其他数的乘积。那么这道题我们照样可以用前缀和。这里同样需要两个数组,前缀和数组yp,后缀和数组np。
算法步骤
- 初始化:定义n,并初始化为nums.length,yp和np数组的长度设置为n。
- 预处理数组:与上道题循环条件,起始位置一致。yp[i]=yp[i-1]+nums[i-1]. np[i]=np[i+1]+nums[i+1].(需要注意的是这里yp[0]和np[n-1]都需要初始化为1,否则相乘时会导致数据出错)
- 数组相乘:这里需要设置数组ans并设置长度为n,用来存储前缀和和后缀和的乘积。
- 返回结果:当前缀和和后缀合相乘完并存储在ans后,返回ans即可。
算法代码
/*** 计算数组中每个元素的乘积,排除自身* 这个方法通过使用两个辅助数组来优化计算,避免了对每个元素重复遍历整个数组求乘积的过程* * @param nums 原始整数数组* @return 包含每个元素对应位置上的乘积结果的数组*/
public int[] productExceptSelf(int[] nums) {// 数组长度int n = nums.length;// yp数组用于存储每个位置左侧所有数字的乘积int[] yp = new int[n];// np数组用于存储每个位置右侧所有数字的乘积int[] np = new int[n];// 初始化左侧乘积数组,yp[0]为1,因为第一个元素左侧没有元素,乘积为1yp[0] = 1;for (int i = 1; i < n; i++) {yp[i] = yp[i - 1] * nums[i - 1];}// 初始化右侧乘积数组,np[n-1]为1,因为最后一个元素右侧没有元素,乘积为1np[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {np[i] = np[i + 1] * nums[i + 1];}// 构建答案数组,每个元素是对应位置的左侧乘积和右侧乘积的乘积int[] ans = new int[n];for (int i = 0; i < n; i++) {ans[i] = yp[i] * np[i];}return ans;
}
时间复杂度为O(n),n为数组长度。
空间复杂度为O(n)
算法示例
以nums = [1,2,3,4]为例
第一步:初始化
n=4
第二步:处理缀合数组
根据yp[i]=yp[i-1]+nums[i-1]可得
yp={1,1,2,6}
根据np[i]=np[i+1]+nums[i+1]可得
np={24,12,4,1}
第三步:缀合数组相乘
ans={24,12,8,6}
第四步:返回结果
此时将ans数组返回即可。
前缀和上篇就先到这里了~
若有不足,欢迎指正~