2024-05-12-前缀和.md

发表于 | 分类于

前缀和是什么

目前看到的题目里面，前缀和比较常出现在区间和相关的题目里面，比如一维数组中求满足连续子数组和为固定值的区段，或者二维数组中求区域面积和。

虽然暴力算法通常也能时间换智力把题算出来，但这违背算法的初衷，前缀和可以通过O(n)的时间复杂度，提供O(1) 时间复杂度获取结果的能力。

最简单的前缀和例题：leetCode1480

这道题的核心就是： preSum[i] = num[i]+preSum[i-1]

其中preSum就是前缀和数组，preSum中的下标为i的数字就是nums中前i个数字之和。

然后代码就很容易给出来

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {

  public int[] runningSum(int[] nums) {
    int[] ans = new int[nums.length];
    ans[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
      ans[i] = ans[i - 1] + nums[i];
    }
    return ans;
  }

}

单独解释一句下标0为啥要单独处理，因为不单独处理会出现num[0-1]。

能解决这个问题，就能大致了解前缀和是什么了。

前缀和的构成和使用

前缀和的构成核心就是：

1
2
3
4
preSum[i] =nums[i]+preSum[i-1]
位置i->j的区间和： num[j]-num[i-1] (有很多算法会把preSum设置成比num长度大1的数组，从下标1开始计数，规避0数组越界的问题，如果这样配置preSum，那么区间和是：preSum[j+1]-preSum[i])
计算前缀和的时间复杂度是O(n),
使用前缀和获取区间和的时间复杂度是O(1)

例题

入门

参照上面的1480就可以了

一维数组 LeetCode303

LeetCode303

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 给定一个整数数组  nums，处理以下类型的多个查询:
 * <p>
 * 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类：
 * <p>
 * NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的
 * 总和 ，
 * <p>
 * 包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )
 */
public class NumArray {

  private static int[] preSum;

  public NumArray(int[] nums) {
    preSum = new int[nums.length];
    preSum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
      preSum[i] = preSum[i - 1] + nums[i];
    }
  }

  public int sumRange(int left, int right) {
    if (left == 0) {
      return preSum[right];
    } else {
      return preSum[right] - preSum[left-1];
    }
  }
}

二维数据（矩阵） LeetCode304

LeetCode304

需要注意的是：

对于二维数组，前缀和变成二维之后，每个点代表以当前点为右下角的矩形内数字和。

也就是对于preSum[5][5]中的preSum[3][3]，3，3这个点代表左上角3*3的范围内所有数字的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 * <p>
 * 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
 * <p>
 * 实现 NumMatrix 类：
 * <p>
 * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 * <p>
 * int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2)
 * 所描述的子矩阵的元素 总和 。
 */
public class NumMatrix {

  private static int[][] preSum;

  public NumMatrix(int[][] matrix) {
    preSum = new int[matrix.length + 1][matrix[0].length + 1];
    for (int i = 1; i < preSum.length; i++) {
      for (int j = 1; j < preSum[i].length; j++) {
        preSum[i][j] = matrix[i - 1][j - 1] + preSum[i][j - 1];
      }
    }
    for (int i = 1; i < preSum[0].length; i++) {
      for (int j = 1; j < preSum.length; j++) {
        preSum[j][i] = preSum[j][i] + preSum[j - 1][i];
      }
    }
    System.out.println("aaa");
  }

  public int sumRegion(int row1, int col1, int row2, int col2) {
    return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1]
        + preSum[row1][col1];
  }
  
}