devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【Java算法专场】前缀和（上）

作者：从前慢现在也慢 | 2024-08-02 19:22:36

赞

踩

【Java算法专场】前缀和（上）

前言

  在求数组或者矩阵求和等问题，我们如果采用暴力解法，时间复杂度可能会达到O(n)或者更高，因此，我们可利用前缀和来解决。

前缀和

前缀和是指序列中的n项和，相当于数学问题中秋数列的前n项和。主要用于数组或列表中求解子数组的和、查询区间和等问题，能够将时间复杂度从O(n)降低到O(1)。

接下来我们就通过题目来更好的来理解前缀和。

【模板】前缀和

算法分析

本道题就是在长度为n的数组中根据输入的区间下标[L,R]来计算区间和。如果我们使用暴力解法，时间复杂度为O(n),但是我们有更优的解法，使用前缀和，能使查询区间和的复杂度降为O(1).

算法步骤

  1. 初始化：根据题目需求，定义变量n,q,l,r，并等待输入。定义数组a长度为（n+1），同理，这里需要借助一个前缀和数组dp，长度也为(n+1);
  2. 预处理：给n,q,数组元素,l,r赋值之后，就可以进行下步操作。
  3. 处理前缀和数组：前缀和数组顾名思义就是用来计算前缀和的大小，（前缀和数组中dp[i]指的是包括i在内之前的元素之和），如果我们每次计算dp[i]都要遍历到i，时间复杂度为O(N^2),但我们可以知道的是，每次计算前缀和，都是dp[i-1]+a[i]（即i之前的前缀和+a[i]).所以我们计算前缀和dp[i]=dp[i-1]+a[i]
  4. 计算区间和：当我们处理完前缀和数组之后，计算[L,R] 的区间和，我们可以理解为计算(R)之前的和减去（L-1）之前的和，即sum=dp[r]-dp[l-1]。
  5. 处理边界：我们这里计算前缀和时，数组下标应该从1开始，若从0开始，当计算前缀和数组dp[0]=dp[-1]+a[0]，就会越界，因此下标应该从1开始。且a[0]=dp[0]=0.
  6. 变量类型：通过题目要求，0<=a[i]<=10^9，因此我们不能使用int类型，而是使用long。

算法代码

  1. import java.util.Scanner;
  2.  
  3. // 注意类名必须为 Main, 不要有任何 package xxx 信息
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner in = new Scanner(System.in);
  7.         int n = in.nextInt();
  8.         int q = in.nextInt();
  9.         long[] a = new long[n + 1];
  10.         long[] dp = new long[n + 1];
  11.         a[0] = dp[0] = 0;
  12.         for (int i = 1; i <= n; i++) {
  13.             a[i] = in.nextLong();
  14.         }
  15.         //处理前缀和数组
  16.         for (int i = 1; i <= n; i++) {
  17.             dp[i] = dp[i - 1] + a[i];
  18.         }
  19.         //计算区间和
  20.         while (q > 0) {
  21.             int l = in.nextInt();
  22.             int r = in.nextInt();
  23.             long sum = dp[r] - dp[l - 1];
  24.             System.out.println(sum);
  25.             q--;
  26.         }
  27.     }
  28. }

时间复杂度为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),会超时，但对于这种求子矩阵和的问题，我们可以使用前缀和来解决。

在说算法步骤之前，先来补充个知识，我们在计算一个矩阵的大小时，其实是可以将分为几部分来求解的，对于本道题的矩阵，我们可以分解为：

算法步骤

  1. 初始化：定义n和m，并创建(n+1)*(m+1)的二维数组a和(n+1)*(m+1)的二维前缀和数组dp。这里是为了防止溢出。同时也需要创建一个(n+1)*(m+1)的前缀和矩阵。
  2. 矩阵处理：在上面的图片中，我们知道了一个矩阵可以切块计算。那么我们在计算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]

即可得到。

算法代码 

  1. import java.util.Scanner;
  2.  
  3. // 注意类名必须为 Main, 不要有任何 package xxx 信息
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc=new Scanner(System.in);
  7.         int n=sc.nextInt();
  8.         int m=sc.nextInt();
  9.         int q=sc.nextInt();
  10.         long[][] a=new long[n+1][m+1];
  11.         long[][] dp=new long[n+1][m+1];
  12.         for(int i=1;i<=n;i++){
  13.             for(int j=1;j<=m;j++){
  14.                 a[i][j]=sc.nextLong();
  15.             }
  16.         }
  17.         //预处理矩阵
  18.         for(int i=1;i<=n;i++){
  19.             for(int j=1;j<=m;j++){
  20.                 //S=(A+B)+(A+C)+D-A
  21.                 dp[i][j]=dp[i-1][j]+dp[i][j-1]+a[i][j]-dp[i-1][j-1];
  22.             }
  23.         }
  24.  
  25.         //求子矩阵和
  26.         while(q>0){
  27.             int x1=sc.nextInt();
  28.             int y1=sc.nextInt();
  29.             int x2=sc.nextInt();
  30.             int y2=sc.nextInt();
  31.             //sum=(A+B+C+D)-(A+B)-(A+C)+A=D
  32.             long sum=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
  33.             System.out.println(sum);
  34.             q--;
  35.         }
  36.     }
  37. }

时间复杂度为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。

算法步骤

  1. 初始化：定义n，并初始化为nums.length.定义两个二维数组yp（前缀合）和np（后缀和）并设置长度为n；yp用来存储从前往后的和，np用来存储从后往前的和。
  2. 预处理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.
  3. 判断：当处理完yp和np之后，我们就可判断yp和np中数组元素是否相等，若相等，证明以该点为中心点的左右区间和相等，返回此时的下标即可。当遍历完数组，若没有相等的，则返回-1.

算法代码

  1.     /**
  2.      * 寻找数组的中心索引
  3.      * 中心索引的左侧元素之和等于右侧元素之和
  4.      * 
  5.      * @param nums 输入的整数数组
  6.      * @return 返回中心索引，如果不存在，则返回-1
  7.      */
  8.     public int pivotIndex(int[] nums) {
  9.         // 数组长度
  10.         int n=nums.length;
  11.         // yp数组用于存储从左侧累加的元素之和
  12.         int[] yp=new int[n];
  13.         // np数组用于存储从右侧累加的元素之和
  14.         int[] np=new int[n];
  15.         
  16.         // 从左侧开始累加，计算每个位置左侧元素之和
  17.         for(int i=1;i<n;i++){
  18.             yp[i]=yp[i-1]+nums[i-1];
  19.         }
  20.         
  21.         // 从右侧开始累加，计算每个位置右侧元素之和
  22.         for(int i=n-2;i>=0;i--){
  23.             np[i]=np[i+1]+nums[i+1];
  24.         }
  25.         
  26.         // 遍历数组，寻找中心索引
  27.         for(int i=0;i<n;i++){
  28.             // 当找到左右两侧元素之和相等的位置时，返回该索引
  29.             if(yp[i]==np[i]){
  30.                 return i;
  31.             }
  32.         }
  33.         // 如果没有找到中心索引，返回-1
  34.         return -1;
  35.     }

算法示例：

以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。

算法步骤

  1. 初始化：定义n，并初始化为nums.length,yp和np数组的长度设置为n。
  2. 预处理数组：与上道题循环条件，起始位置一致。yp[i]=yp[i-1]+nums[i-1]. np[i]=np[i+1]+nums[i+1].(需要注意的是这里yp[0]和np[n-1]都需要初始化为1，否则相乘时会导致数据出错）
  3. 数组相乘：这里需要设置数组ans并设置长度为n，用来存储前缀和和后缀和的乘积。
  4. 返回结果：当前缀和和后缀合相乘完并存储在ans后，返回ans即可。

算法代码

  1. /**
  2.  * 计算数组中每个元素的乘积，排除自身
  3.  * 这个方法通过使用两个辅助数组来优化计算，避免了对每个元素重复遍历整个数组求乘积的过程
  4.  * 
  5.  * @param nums 原始整数数组
  6.  * @return 包含每个元素对应位置上的乘积结果的数组
  7.  */
  8. public int[] productExceptSelf(int[] nums) {
  9.     // 数组长度
  10.     int n = nums.length;
  11.     // yp数组用于存储每个位置左侧所有数字的乘积
  12.     int[] yp = new int[n];
  13.     // np数组用于存储每个位置右侧所有数字的乘积
  14.     int[] np = new int[n];
  15.     
  16.     // 初始化左侧乘积数组，yp[0]为1，因为第一个元素左侧没有元素，乘积为1
  17.     yp[0] = 1;
  18.     for (int i = 1; i < n; i++) {
  19.         yp[i] = yp[i - 1] * nums[i - 1];
  20.     }
  21.     
  22.     // 初始化右侧乘积数组，np[n-1]为1，因为最后一个元素右侧没有元素，乘积为1
  23.     np[n - 1] = 1;
  24.     for (int i = n - 2; i >= 0; i--) {
  25.         np[i] = np[i + 1] * nums[i + 1];
  26.     }
  27.     
  28.     // 构建答案数组，每个元素是对应位置的左侧乘积和右侧乘积的乘积
  29.     int[] ans = new int[n];
  30.     for (int i = 0; i < n; i++) {
  31.         ans[i] = yp[i] * np[i];
  32.     }
  33.     
  34.     return ans;
  35. }

时间复杂度为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数组返回即可。

前缀和上篇就先到这里了~

若有不足，欢迎指正~ 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/919525
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号