【算法系列篇】前缀和-1-阿里云开发者社区

前言

前缀和算法是一种常用的优化技术，用于加速某些涉及连续子数组或子序列求和的问题。它基于一个简单但强大的思想，通过提前计算并存储数组的前缀和，以便在后续查询中可以快速获取任意区间的和。

在许多算法问题中，我们需要频繁地查询子数组的和，例如最大子数组和、连续子数组的平均值等。传统的方法是在每次查询时遍历数组，并计算所需区间的和，这样会导致时间复杂度较高。

而前缀和算法通过预处理数组，计算出每个位置的前缀和，并将其保存在一个额外的数组中。这样，在查询时，我们只需要简单地减去两个前缀和即可得到所需子数组的和，从而将查询时间降低为O(1)的常数复杂度。

什么是前缀和算法

前缀和算法（Prefix Sum Algorithm）是一种用于高效计算数组前缀和的算法。前缀和是指数组中某个位置之前（包括该位置）所有元素的和。

前缀和算法的基本思想是通过一次遍历数组，计算每个位置的前缀和，并将其存储在一个新的数组中。然后，可以通过查询新数组中的元素，快速计算出任意子数组的和。

具体步骤如下：

创建一个新的数组prefixSum，长度与原数组相同。
初始化prefixSum[0]为原数组的第一个元素。
从原数组的第二个元素开始，依次计算prefixSum[i] = prefixSum[i-1] + nums[i]，其中nums为原数组。
完成后，prefixSum数组中的每个元素即为对应位置之前所有元素的和

通过前缀和算法，可以在O(1)的时间复杂度内计算出任意子数组的和。例如，要计算原数组中从位置i到位置j的子数组和，只需计算prefixSum[j] - prefixSum[i-1]即可。如果i为0，则直接返回prefixSum[j]。

前缀和算法在解决一些与子数组和相关的问题时非常有用，例如求解子数组和等于目标值的个数、求解最大子数组和、求解最长连续子数组和等。

1.【模板】前缀和

https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

1.1 题目要求

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);
        }
    }
}

1.2 做题思路

按照暴力解法的思路，每次查询 l 到 r 之间的和的时候，就需要遍历一次数组，那么这样的时间复杂度就是 O(q*n) 了，因为进行了较多的重复计算，导致时间效率较低，那么是否有一种方法可以减少重复计算呢？答案是有的，这就是前缀和的思路，其实有点类似于前面我为大家分享的滑动窗口中进窗口的操作，每次进窗口更新数据的时候只需要用前面已经计算了的数字的和加上进窗口的那个数据，就得到了当前位置之前所有元素的和。通过这样的思路就大大减少了重复计算。

然后这个求 l 到 r 之间元素的和的时候，就只需要用 r 和 r 之前所有元素的和减去 l 之前所有元素的和就可以了。

并且仔细的人可能会发现：为什么 l 和 r 都是从1开始而不是0呢？因为从下标为0开始的话，就需要求0 ~ -1 之间元素的和，但是这个区间是不合法的，所以数组从 1 开始就可以防止出现这种的情况。

在开始求 l 到 r 之间元素的和的时候，可以先对数组进行一个预处理，求出数组中每个位置之前的前缀和。

1.3 Java代码实现

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt(),q = in.nextInt();
            int[] arr = new int[n + 1];
            for(int i = 1; i <= n; i++) arr[i] = in.nextInt();
            //创建一个同样大小的前缀和数组，并且因为是多个元素的和，
            //可能会超出int所能表示的最大范围，这里用long来表示
            long[] dp = new long[n + 1]; 
            for(int i = 1; i <= n; i++) {
                dp[i] = dp[i-1] + arr[i];
            }
            for(int i = 0; i < q; i++) {
                int l = in.nextInt(),r = in.nextInt();
                System.out.println(dp[r] - dp[l-1]);
            }
        } 
    }
}

2. 【模板】二维前缀和

https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

2.1 题目要求

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);
        }
    }
}

2.2 做题思路

二维前缀和和一维前缀和的思路基本上相同的，只是一个是一维数组，一个是二维数组，一些处理细节不同。

当求 dp[i][j] 的时候，可以将 dp 数组分成 A、B、C、D 四个部分，A 部分是从 0，0 位置开始到 i - 1，j - 1 位置之间的矩阵元素的和。dp[i][j] = A + B + C + D 之间的元素的和，但是这里 B 和 C 区间之间的元素不是很容易求和，所以我们可以用

(A + B) + (A + C) + D - A 来求 dp[i][j] 的值。

然后(x1,y1) 到 (x2,y2)之间的矩阵的和，我们可以使用 dp[x2][y2] - (A + B) - (A + C) + A，也就是 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]。

2.3 Java代码实现

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt(),m = in.nextInt(),q = in.nextInt();
            int[][] arr = new int[n + 1][m + 1];
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    arr[i][j] = in.nextInt();
                }
            }
            //构造二维前缀和数组
            long[][] dp = new long[n + 1][m + 1];
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
                }
            }
            for(int i = 0; i < q; i++) {
                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]);
            }
        }
    }
}

3. 寻找数组的中心下标

https://leetcode.cn/problems/find-pivot-index/description/

3.1 题目要求

给你一个整数数组 nums ，请计算数组的中心下标。

数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示：

1 <= nums.length <= 104
-1000 <= nums[i] <= 1000

class Solution {
    public int pivotIndex(int[] nums) {
    }
}

3.2 做题思路

这个题目要求我们找到一个元素，这个元素的左边所有元素的和等于该元素右边所有元素的和，通过前面的两个题目我们做这道题目应该是会有一点思路的。

因为要求的是某一元素左边部分和前面部分的元素的和，所以我们可以使用两个数组，分别记录数组中每一个元素的前缀和以及后缀和，前缀和数组从前往后插入数据，后缀和数组从后往前插入数据，并且前缀和的第一个数据为0，后缀和的最后一个数据为0。最后再遍历一次数组，判断数组某一位置的前缀和是否等于后缀和。

3.3 Java代码实现

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];  //前缀和数组
        int[] g = new int[n];  //后缀和数组
        for(int i = 1; i < n; i++) {
            f[i] = f[i-1] + nums[i - 1];
        }
        for(int i = n - 2; i >= 0; i--) {
            g[i] = g[i + 1] + nums[i + 1];
        }
        for(int i = 0; i < n; i++) {
            if(f[i] == g[i]) return i;
        }
        return -1;
    }
}

4. 除自身以外的数组的乘积

https://leetcode.cn/problems/product-of-array-except-self/

4.1 题目要求

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30

保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内

class Solution {
    public int[] productExceptSelf(int[] nums) {
    }
}

4.2 做题思路

这个题目跟上面的寻找数组的中心下标思路基本上差不多，只是判断前缀和和后缀和相等的操作换成了前缀积和后缀积的乘积，这里我就不过多介绍了，大家可以直接看代码。

4.3 Java代码实现

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        //这里需要注意前缀积的第一个元素和后缀积的最后一个元素要初始化为1，因为是乘法
        f[0] = 1;
        g[n-1] = 1;
        for(int i = 1; i < n; i++) {
            f[i] = f[i - 1] * nums[i - 1];
        }
        for(int i = n-2; i >= 0; i--) {
            g[i] = g[i + 1] * nums[i + 1];
        }
        int[] ret = new int[n];
        for(int i = 0; i < n; i++) {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
}

【算法系列篇】前缀和-2：https://developer.aliyun.com/article/1430519

【算法系列篇】前缀和-1

前言