前缀和技巧详解：和为 K、被 K 整除、连续数组及矩阵区域和

1. 和为 K 的子数组

题目链接：560. 和为 K 的子数组

算法思路：前缀和 + 哈希表

sum[i] 表示（0，i）之间的前缀和，当 x 为起始位置，i 元素结尾的数组和为 k 时，也就是相当于在（0，x）区间前缀和为 sum - k，因此也就是求出在（0，i-1）内有多少个前缀和为 sum - k 的数组即可。

但是也不需要真的定义一个前缀和，使用 sum 累加计算即可。前缀和处理的时机应该是遍历到哪个元素，就计算哪个元素之前的前缀和，因为当整个前缀和都预处理出来时，在哈希表中寻找可能会重复还未遍历到的元素的前缀和。

算法代码：

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> hash = new HashMap<>();
    hash.put(0, 1);
    int sum = 0, ret = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        ret += hash.getOrDefault(sum - k, 0);
        hash.put(sum, hash.getOrDefault(sum, 0) + 1);
    }
    return ret;
}

2. 和可被 k 整除的子数组

题目链接：974. 和可被 k 整除的子数组

算法思路：前缀和 + 哈希表

该题和上道题基本类似，只不过用到了同余定理：(a - b) % k == 0 得到 a % k == b % k，该题也就是找在（0，i-1）区间内有多少个前缀和的余数为 sum[i] % k。

细节：前缀和中存的应该是前缀和的余数。

算法代码：

public int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> hash = new HashMap<>();
    hash.put(0, 1);
    int sum = 0, ret = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        int r = (sum % k + k) % k;
        ret += hash.getOrDefault(r, 0);
        hash.put(r, hash.getOrDefault(r, 0) + 1);
    }
    return ret;
}

3. 连续数组

题目链接：525. 连续数组

算法思路：前缀和 + 哈希表

该题可进行一个转换处理，那就是将元素 0 转换为 -1 处理，那么 0 和 1 数量相同的子数组就是 sum 和为 0 的数组，此时就和上面的查找和为 k 的数组基本一样了，就是找和为 0 的数组。

细节问题：

• 此时哈希表中存的应该是 sum 和元素下标，因为该题返回的是数组长度。
• 当遇到重复的 sum 时，不需要重复的将下标存入哈希表，因为返回最长的数组长度，当前面有下标存入时，当遇到重复的 sum，之前的下标一定小于现在的，因此可以跳过。
• 计算长度，当计算长度时需要判断当前的结果是否大于之前的结果。
• 还需要提前存入哈希表 0 的值的下标为 -1，因为当整个数组为 sum 时，会去 -1 的位置找 sum = 0，因此做提前处理。

算法代码：

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> hash = new HashMap<>();
    hash.put(0, -1);
    int ret = 0, sum = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) nums[i] = -1;
        sum += nums[i];
        if (hash.containsKey(sum)) ret = Math.max(ret, i - hash.get(sum));
        else hash.put(sum, i);
    }
    return ret;
}

4. 矩阵区域和

题目链接：1314. 矩阵区域和

题意，如图：

answer[i][j] 的值就是当前元素上下左右扩展 k 格的元素和。

算法思路：使用二维前缀和

首先预处理一个二维前缀和，和之前的二维前缀和定义相同。然后遍历元素计算该元素的 answer，但是注意细节，当 i-k，j-k 时可能会越界，此时需要使用边界 0，因此使用 Math.max 方法，也就是坐标为 Math.max(i-k,0)；同样的 i+k 时也会越界，因此使用 min 即可。

还有细节问题要处理，就是前缀和定义时需要定义为 m+1 和 n+1，否则计算前缀和时边界问题会很麻烦，但是处理前缀和时对应的原数组的下标应该减一计算；同样的，当计算结果数组时，前缀和下标应该加一计算。

算法代码：

public int[][] matrixBlockSum(int[][] mat, int k) {
    int m = mat.length, n = mat[0].length;
    int[][] dp = new int[m + 1][n + 1];
    // 预处理前缀和
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
        }
    }
    // 使用前缀和
    int[][] ret = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int x1 = Math.max(i - k, 0) + 1, y1 = Math.max(j - k, 0) + 1;
            int x2 = Math.min(i + k, m - 1) + 1, y2 = Math.min(j + k, n - 1) + 1;
            ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
        }
    }
    return ret;
}