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

算法代码

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

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

算法步骤

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]**

即可得到。

算法代码

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-A
                dp[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=D
            long 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。

算法步骤

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.

算法代码

    /**
     * 寻找数组的中心索引
     * 中心索引的左侧元素之和等于右侧元素之和
     * 
     * @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;
            }
        }
        // 如果没有找到中心索引，返回-1
        return -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。

算法步骤

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即可。

算法代码

/**
 * 计算数组中每个元素的乘积，排除自身
 * 这个方法通过使用两个辅助数组来优化计算，避免了对每个元素重复遍历整个数组求乘积的过程
 * 
 * @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，因为第一个元素左侧没有元素，乘积为1
    yp[0] = 1;
    for (int i = 1; i < n; i++) {
        yp[i] = yp[i - 1] * nums[i - 1];
    }
    
    // 初始化右侧乘积数组，np[n-1]为1，因为最后一个元素右侧没有元素，乘积为1
    np[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数组返回即可。

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

若有不足，欢迎指正~