【算法】前缀和

爱被打了一巴掌 2023-10-07 22:36 15阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现
 *   *  2.1.一维前缀和
     *  2.2.二维前缀和
 *  3.应用
 *   *  3.1.应用一
     *  3.2.应用二

> 本文参考：  
> [LABULADONG 的算法网站][LABULADONG]

## 1.概述 ##

前缀和算法分为一维和二维，一维前缀和可以**快速求序列中某一段的和**，而二维前缀和可以**快速求一个矩阵中某个子矩阵的和**。

## 2.代码实现 ##

### 2.1.一维前缀和 ###

（1）实现代码如下：

class NumArray {
        
        //前缀和数组，preSum[i] 表示 nums[0...i - 1] 的累加和
        private int[] preSum;
        
        //输入数组 nums，构造前缀和
        public NumArray(int[] nums) {
        
            // preSum[0] = 0，便于计算累加和
            preSum = new int[nums.length + 1];
            for (int i = 1; i < preSum.length; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
        }
        
        //查询闭区间 nums[left, right] 的累加和
        public int sumRange(int left, int right) {
        
            return preSum[right + 1] - preSum[left];
        }
    }

（2）下面对代码中一些细节进行说明：

*  前缀和数组 preSum 的长度之所以设置为 nums.length + 1 而非 nums.length，其原因在于方便计算累加和；
 *  preSum\[i\] 表示 nums\[0…i - 1\] 的累加和，那么推导出 preSum\[i\] = preSum\[i - 1\] + nums\[i - 1\]，如下图所示：  
    ![在这里插入图片描述][c9591bc068894fc6bdabf3d1b5778267.png]
 *  在有了前缀和数组 preSum 后，如果想要查询区间 nums\[i…j\] 的累加和，那么计算 preSum\[j + 1\] - preSum\[i\] 的值即可，如下图所示：  
    ![在这里插入图片描述][d6fbaa7b16c84cb98d6338dd3977bb5f.png]

### 2.2.二维前缀和 ###

（1）实现代码如下：

class NumMatrix {
        
        // preSum[i][j] 表示矩阵 matrix 中左上角坐标为 [0, 0]、右下角坐标为 [i - 1, j - 1] 的子矩阵的元素和
        private int[][] preSum;
        
        public NumMatrix(int[][] matrix) {
        
            int m = matrix.length;
            int n = matrix[0].length;
            if (m == 0 || n == 0) {
        
                return;
            }
            //构造前缀和矩阵
            preSum = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    // 计算每个左上角坐标为 [0, 0]、右下角坐标为 [i - 1, j - 1] 的子矩阵的元素和
                    preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
                }
            }
        }
        
        //计算矩阵 matrix 中左上角坐标为 [x1, y1]、右下角坐标为 [x2, y2] 的子矩阵的元素和
        public int sumRegion(int x1, int y1, int x2, int y2) {
        
            return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
        }
    }

（2）下面对代码中一些细节进行说明：

*  设下图中绿色子矩阵的左上角坐标为 \[x1, y1\]、右下角坐标为 \[x2, y2\]，那么它可以由下图中右边的 4 个子矩阵通过加减组合得到：

![在这里插入图片描述][99e94f690d8041a084781b7bebd8982e.png]

*  在初始化前缀和矩阵 preSum 时，需要计算每个左上角坐标为 \[0, 0\]、右下角坐标为 \[i - 1, j - 1\] 的子矩阵的元素和，此时只需要将上面的等式稍作变换即可，如下图所示。不过需要注意的是**绿色子矩阵的边长为 1，即对应矩阵 matrix 中的一个元素**。

![在这里插入图片描述][9aff734cdeec49548462a528689f0e82.png]

## 3.应用 ##

前缀和算法的使用场景：`原数组/矩阵在不会被修改的前提下，频繁地对其某个区间/子矩阵的累加和进行查询操作`。如果只需要查询一次，那么使用前缀和算法的意义不大；而如果频繁地进行查询操作，那么前缀和算法的优势便体现出来了：

*  在构建前缀和数组/矩阵时，其时间复杂度为 O(n) / O(mn)，而在频繁地进行查询操作时，其时间复杂度仅为 O(1)；
 *  如果直接进行累加操作，则需要进行多次时间复杂度为 O(n) / O(mn) 的操作（注：此处的 n 和 mn 取决于要查询的区间 / 子矩阵大小）。

### 3.1.应用一 ###

下面以 LeetCode 中的[304.二维区域和检索 - 矩阵不可变][304._ -]这题为例来说明**前缀和的基础用法**：

![在这里插入图片描述][aad0144515834a4eae2550d1a37732c8.png]

本题就是典型地要频繁地对其矩阵 matrix 中的子矩阵的累加和进行查询操作，其对应的实现代码如下：

class NumMatrix {
        
        /*
            前缀和矩阵preSum记录矩阵matrix[0,0,i,j]的元素和
            preSum[i][j]=左上角(0,0)、右下角(i-1,j-1)所描述的子矩阵的元素总和
        */
        private int[][] preSum;
        
        public NumMatrix(int[][] matrix) {
        
            int m = matrix.length, n = matrix[0].length;
            //构造前缀和矩阵
            preSum = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
                }
            }
        }
        
        //计算左上角(row1, col1)、右下角(row2, col2)所描述的子矩阵的元素总和
        public int sumRegion(int row1, int col1, int row2, int col2) {
        
            return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
        }
    }
    
    /**
     * Your NumMatrix object will be instantiated and called as such:
     * NumMatrix obj = new NumMatrix(matrix);
     * int param_1 = obj.sumRegion(row1,col1,row2,col2);
     */

### 3.2.应用二 ###

除了应用一中的基础用法之外，**前缀和还常常与哈希表一起使用**，以达到进一步降低时间复杂度的目的（本质是空间换时间），下面以 LeetCode 中的 [560.和为 K 的子数组][560._ K]这题为例：

![在这里插入图片描述][1183f60cc5634f27a9018a516310d03d.png]

显然，本题可以直接使用前缀和数组 preSum 来保存 nums 的前缀和，然后再使用 2 个 for 循环来遍历并判断所有的子数组，最终返回和为 k 的连续子数组的个数即可，具体代码实现如下：

class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            int length = nums.length + 1;
            int[] preSum = new int[length];
            for (int i = 1; i < length; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            int cnt = 0;
            for (int i = 0; i < length - 1; i++) {
        
                for (int j = i + 1; j < length; j++) {
        
                    // preSum[j] - preSum[i] 即为数组 nums 中连续子数组[i, j)的和
                    if (preSum[j] - preSum[i] == k) {
        
                        cnt++;
                    }
                }
            }
            return cnt;
        }
    }

但是，该方法时间复杂度为 O(n2)，其主要原因在于该代码中有一个 2 层 for 循环，那么我们能不能进一步地降低时间时间复杂度呢？答案是肯定的。具体思路如下所示：

*  首先，我们注意到第 2 个 for 循环的作用在于**查找以 nums\[i\] 为起点（包括）、以 nums\[j\] 为终点（不包括）的子数组的和为 k 的个数，也就是在计算有多少个 j 能够使得 preSum\[j\] - preSum\[i\] == k**。通过分析发现，题目的要求是返回和为 k 的连续子数组的个数，而并**不用返回具体是哪些数组**。
 *  所以可以使用哈希表做如下优化：使用 preSumMap 记录前缀和以及其对应出现的次数，那么当 preSumMap.containsKey(preSum\[j\] - k) 时，直接更新 cnt 即可，具体的代码实现如下所示：

class Solution {
        
        public int subarraySum(int[] nums, int k) {
        
            int n = nums.length;
            Map<Integer, Integer> preSumMap = new HashMap<>();
            preSumMap.put(0, 1);
            int res = 0;
            // sum0_i 记录 nums[0...i] 之和
            int sum0_i = 0;
            // sum0_j 记录 nums[0...j] 之和，i < j
            int sum0_j = 0;
            for (int j = 0; j < n; j++) {
        
                sum0_j += nums[j];
                // sum0_j - sum_i = k
                sum0_i = sum0_j - k;
                res += preSumMap.getOrDefault(sum0_i, 0);
                preSumMap.put(sum0_j, preSumMap.getOrDefault(sum0_j, 0) + 1);
            }
            return res;
        }
    }

这样一来，前缀和 + 哈希表使得上述代码的时间复杂度从 O(n2) 降低为 O(n)。最后，大家可以去 LeetCode 上找相关的前缀和的题目来练习，或者也可以直接查看[LeetCode算法刷题目录 (Java)][LeetCode_ _Java]这篇文章中的前缀和的章节。如果大家发现文章中的错误之处，可在评论区中指出。

[LABULADONG]: https://labuladong.gitee.io/algo/
[c9591bc068894fc6bdabf3d1b5778267.png]: https://img-blog.csdnimg.cn/c9591bc068894fc6bdabf3d1b5778267.png
[d6fbaa7b16c84cb98d6338dd3977bb5f.png]: https://img-blog.csdnimg.cn/d6fbaa7b16c84cb98d6338dd3977bb5f.png
[99e94f690d8041a084781b7bebd8982e.png]: https://img-blog.csdnimg.cn/99e94f690d8041a084781b7bebd8982e.png
[9aff734cdeec49548462a528689f0e82.png]: https://img-blog.csdnimg.cn/9aff734cdeec49548462a528689f0e82.png
[304._ -]: https://leetcode-cn.com/problems/range-sum-query-2d-immutable
[aad0144515834a4eae2550d1a37732c8.png]: https://img-blog.csdnimg.cn/aad0144515834a4eae2550d1a37732c8.png
[560._ K]: https://leetcode.cn/problems/subarray-sum-equals-k/
[1183f60cc5634f27a9018a516310d03d.png]: https://img-blog.csdnimg.cn/1183f60cc5634f27a9018a516310d03d.png
[LeetCode_ _Java]: https://blog.csdn.net/weixin_43004044/article/details/122477673