前缀和问题2

1. 和为 K 的子数组（560）

题目描述：

算法原理：
我们先针对数组的0到i区间进行分析，题目要求我们求出和为k的子数组个数，于是我们需要在0到i这个区间内去找结尾为i位置元素并且和为k的子数组个数，0到i这个区间的和为sum，那么问题可以转换为找到0到i-1区间内的前缀和为sum-k的个数，那么题目的返回值就是遍历数组后以不同的i为结尾的满足条件的子数组的个数的和。这里无需去建立一个前缀和数组，我们可以使用的是滚动数组的那种思想设置一个变量来记录前缀和，与此同时维护一个哈希表来保存前缀和与对应次数的键值对。另外我们需要提前防止一个（0，1）的键值对到哈希表中，因为这是当0到i区间内元素和等于k的特殊情况。
代码如下：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int ret = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        for (int x : nums) {
            sum += x;
            ret += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }
}

题目链接

2. 和可被 K 整除的子数组（974）

题目描述：

算法原理：
这一题首先要知道两个知识点第一个就是（a-b）%c等于0，此时说明a和b模c的余数是相等的，就是同余定理。第二个就是在Java当中一个负数取余取出来的值也是个负数，所以我们要将这个负数恢复成正数得到正确的余数，假设这里的a%c，我们加上c得到a%c+c，但是同时我们又需要去考虑到正数取余的情况，所以我们需要再去取余一次，最终得到取余的公式为(a%c+c)%c。
题目要求我们去找到数组中元素和能够整除k的子数组，并且要返回总的满足题目条件的子数组数目。

如上图，我们还是和上一题相似的思想，如果说我们单独考虑0到i区间，也就是要求满足条件的子数组必须以第i个元素为结尾时，那么要使得子数组能够整除k，我们可以将题目转换成要求（sum-前缀和）%k等于0，然后根据同余定理，我们只需要去找到和sum%k相等的（前缀和%k）中的前缀和即可，然后取余的运算要考虑到负数的情况，代码的编写和上题类似，但是代码中还有一个细节就是需要在进行上述操作之前给哈希表中先放一个（0，1）的键值对，因为我们代码中的哈希表是存放（0到i-1区间的不同前缀和模k，个数）这样的键值对的，题目中存在一种特殊情况就是sum自己就能够整除k，此时的满足条件的子数组就是sum，前缀和就是0，出现这种情况最终返回的子数组数量也要加一，所以要先放入（0，1）键值对。
代码如下：

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int sum = 0, ret = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0 ,1);
        for (int x : nums) {
            sum += x;
            int temp = (sum % k + k) % k;
            ret += map.getOrDefault(temp, 0);
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }

        return ret;
    }
}

题目链接

3. 连续数组（525）

题目描述：

算法原理：
这题和上面两题的思想是一致的，代码也是类似的。
题目要求我们找到包含相同数量的0和1的最长连续子数组，如果我们把整个数组的0改成-1，那么这题就变成了去找到元素和为0的最长连续子数组，那么就和第一题很相似了，只不过第一题返回的是个数，而我们这里返回的是最大长度。然后还是第一题的思想既然要找总和为0的子数组，那么针对0到i区间的数组分析，我们只需要能够去找到在区间内的值为sum的前缀和（因为sum-0=sum），然后再将此时的i减去j即可得到满足题目条件的子数组的长度。要特别注意的一个细节就是，0到i区间的sum可能直接就等于0了，所以我们要提前在哈希表中加入（0，-1）这样的键值对。
代码如下：

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, -1);

        int sum = 0;
        int ret = 0;
        for (int i = 0; i < nums.length; i++) { 
            sum += nums[i] == 0 ? -1 : 1;
            if (map.containsKey(sum)) {
                ret = Math.max(ret, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }

        return ret;
    }
}

题目链接

4. 矩阵区域和（1314）

题目描述：

算法原理：
根据题目意思我们需要去计算得到一个和mat数组相同尺寸的数组answer去返回，至于这个answer计算的方式比较特殊，我们举例当k=1时：

如图所示当k=1时，我们要计算answets[0][0]的话就需要将红色框内累加，计算answer[0][1]的话就需要将绿色框内累加，answer[0][3]就要将黄色框内数字累加，如果求answer[1][1]就需要将整个矩阵累加，其他位置也是类似，其实就是将位置的横纵坐标加一减一范围内的数字累加，对于其它的k值也是类似。
那么我们观察蓝色的范围，其实就是9这个数字位置对应的范围，假设坐标为i和j，我们能够发现左上角和右下角坐标分别为(i-1,j-1)以及(i+1,j+1)，求蓝色框范围内的数字和完全可以使用二维前缀和的方式来解决。
具体的流程就是先求出mat数组对应的二维前缀和矩阵，然后通过前缀和矩阵解出k值下不同的矩阵和填入answer矩阵返回。
代码如下：

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int 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][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int[][] answer = 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;
                int y1 = Math.max(j - k, 0) + 1;
                int x2 = Math.min(i + k, m - 1) + 1;
                int y2 = Math.min(j + k, n - 1) + 1;
                answer[i][j] = dp[x2][y2] + dp[x1 - 1][y1 - 1] - dp[x1 - 1][y2] - dp[x2][y1 - 1];
            }
        }

        return answer;
    }
}

题目链接