前缀和数组系列

涉及三道题：
303. 区域和检索 - 数组不可变
304. 二维区域和检索 - 矩阵不可变
560. 和为 K 的子数组

如果要得到「区间和」，能想到最简单的方法就是遍历所求区间，循环相加即可。如果这种需求有很多，此时，时间复杂度为 O(n^2)
基于上面描述的场景，我们完全可以使用「前缀和」优化，前缀和数组中每个元素的值为区间[0…i]的元素和。

注意：
前缀和适用于不变数组；对于变化的数组，可以使用「线段树」，关于线段树的详细介绍可见 线段树详解
区域和检索 - 数组不可变

区域和检索 - 数组不可变

题目详情可见 ：区域和检索 - 数组不可变

建议：preSum[]整体向后偏移一位，简便处理

如果求区间[2,4]的和，只需计算preSum[4 + 1] - preSum[2]即可

代码：

class NumArray {
    // 记录前缀和的数组
    private int[] preSum;
    public NumArray(int[] nums) {
        // preSum 从 1 开始，避免越界问题
        preSum = new int[nums.length + 1];
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二维区域和检索 - 矩阵不可变

题目详情可见 ：二维区域和检索 - 矩阵不可变

如果求红色区间的和，只需求preSum[4,4] - preSum[1,4] - preSum[4,1] + preSum[1,1]即可
● preSum[4,4]：黄 + 蓝 + 绿 + 红
● preSum[1,4]：黄 + 蓝
● preSum[4,1]：黄 + 绿
● preSum[1,1]：黄

代码：

class NumMatrix {
    private int[][] preSum;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }
    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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

和为 K 的子数组

题目详情可见 和为 K 的子数组
借鉴「两数和」的思路，利用HashMap。

代码：

public int subarraySum(int[] nums, int k) {

    Map<Integer, Integer> preSum = new HashMap<>();
    preSum.put(0, 1);

    int sum = 0;
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        int target = sum - k;
        if (preSum.containsKey(target)) res += preSum.get(target);
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16