前缀和数组

303. 区域和检索 - 数组不可变

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

560. 和为 K 的子数组

如果要得到「区间和」，能想到最简单的方法就是遍历所求区间，循环相加即可。如果这种需求有很多，此时，时间复杂度为 $O(n^2)$$O(n^2)$

基于上面描述的场景，我们完全可以使用「前缀和」优化，前缀和数组中每个元素的值为区间[0..i]的元素和

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

区域和检索 - 数组不可变

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

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

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

下面给出详细代码：

xxxxxxxxxx
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];
    }
}

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

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

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

• preSum[4,4]：黄 + 蓝 + 绿 + 红
• preSum[1,4]：黄 + 蓝
• preSum[4,1]：黄 + 绿
• preSum[1,1]：黄

下面给出详细代码：

xxxxxxxxxx
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];
    }
}

和为 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;
}