前缀和

下面给出两个例子。

  • 第一个是给定 target，计算和为 target 的子数组的数目；
  • 第二个是给定 target，计算和为 target 的子数组的最短的长度。

解题的核心思想都是一致的：

  1. 使用 Map 记录出现过的 prefix_sum 的数目/最近下标。
  2. 处理特殊值，即将 0 放入 Map 中。
  3. 进入循环：
    1. 查找 Map 中是否存在 prefix_sum - target 的值，更新 res。
    2. 把本轮循环的 prefix_sum 放入 Map 中。
  4. 退出循环，返回 res。

560. 和为 K 的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int subarraySum(int[] nums, int target) {
        int len = nums.length;
        int[] presums = new int[len + 1];
        for (int i = 1; i <= len; ++i) {
            presums[i] = presums[i - 1] + nums[i - 1];
        }
        
        int res = 0;  // 计算组成 target 的子数组的组合的数目
        Map<Integer, Integer> cnts = new HashMap<>();  // [presum, idx]        
        cnts.put(0, 1);
        for (int i = 1; i <= len; ++i) {
            int presum = presums[i];   
            res += cnts.getOrDefault(presum - target, 0);  
            // 作为被比较的对象
            cnts.put(presum, cnts.getOrDefault(presum, 0) + 1);       
        }
        return res;
    }
}

1590. 使数组和能被 P 整除

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
class Solution {
    public int minSubarray(int[] nums, int p) {
        int len = nums.length;
        int[] presums = new int[len + 1];
        for (int i = 0; i < len; ++i) {
            presums[i + 1] = (presums[i] + nums[i]) % p;
        }
        int target = presums[len]; 
        if (target == 0) return 0;

        int res = len;  // 组成 target 的子数组的最短长度
        Map<Integer, Integer> records = new HashMap<>();     
        records.put(0, 0);
        for (int i = 1; i <= len; ++i) {            
            int presum = presums[i];                     
            
            int search = ((presum - target) % p + p) % p;
            if (records.containsKey(search)) {
                res = Math.min(res, i - records.get(search));
            }
            // 作为被比较的对象
            records.put(presum, i);   
        }
        return res == len ? -1 : res;
    }
}

二维前缀和

在求二维前缀和的时候，仅需注意两个点：

  • presums 比 matrix 的长宽都大 1。
  • 在计算子矩阵和的时候，rowbig 和 colbig 都要记得加 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumMatrix {
    int[][] presums;
    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        this.presums = new int[row + 1][col + 1];
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                presums[i + 1][j + 1] = presums[i][j + 1] + presums[i + 1][j] - presums[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return presums[row2 + 1][col2 + 1] + presums[row1][col1] - presums[row1][col2 + 1] - presums[row2 + 1][col1];
    }
}