前缀和算法专题（2）
找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-ZEEKLOG博客
所属专栏： 优选算法专题
对于 "前缀和" 不是很了解的小伙伴一定要去看下面这篇博客：前缀和算法的介绍
目录
560. 和为K 的子数组
题目：
给你一个整数数组nums和一个整数k，请你统计并返回 该数组中和为k的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：输入：nums = [1,1,1], k = 2 输出：2
示例 2：输入：nums = [1,2,3], k = 3 输出：2
提示：1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
思路：这种求子数组的题目，暴力枚举应该是很容易能够想到的。暴力枚举的做法就是固定一个起始下标，寻找符合题目要求的结束下标即可。
代码实现：
class Solution { public int subarraySum(int[] nums, int k) { // 暴力枚举： int n = nums.length; int count = 0; for (int i = 0; i < n; i++) { // 固定起始下标 int sum = 0; for (int j = i; j < n; j++) { // 寻找结束下标 sum += nums[j]; if (sum == k) { count++; } } } return count; } }如果是一路跟着我们刷过来的小伙伴，看到这一题，肯定会将优化的想法往滑动窗口上面去靠拢。因为在滑动窗口算法中，我们得出了一个结论：对于子序列的问题，求解的方法往往是此方法。但是这里比较特殊。因为题目告诉我们了，这里数据会出现0和负数，因此和为k的子数组可能会出现下面这种情况：
因此，这里的优化不能使用滑动窗口算法。 这个优化方法估计也只有大佬们才能想到了。
这里之所以转变为求sum[i] - k，是因为这个刚好是前缀和，符合前缀和数组的要求。
处理思路：首先，计算出前缀和，再去前缀和数组中寻找值为 sum[i] - k 的个数有多少即可。
class Solution { public int subarraySum(int[] nums, int k) { // 用哈希表记录前缀和 Map<Integer, Integer> hash = new HashMap<>(); hash.put(0, 1); // 处理k等于sum[i]的情况 int sum = 0; // 记录前缀和 int count = 0; // 记录和为k的子数组的个数 for (int i = 0; i < nums.length; i++) { sum += nums[i]; // i位置的前缀和 // 寻找sum-k的个数 count += hash.getOrDefault(sum-k, 0); hash.put(sum, hash.getOrDefault(sum ,0)+1); } return count; } }代码分析：
注意：这个题目中有一些细节问题要注意。
1、我们之所以不先去将前缀和数组计算出来，是因为前缀和数组是先要遍历的，而我们最终求的个数的时候，也是要遍历的，因此我们完全可以将求前缀和数组的过程并入遍历数组求最终结果的过程。
2、我们这里求最终结果的过程，其实和暴力枚举的出发点是一样的，都是通过固定一个位置（起始或者结束）然后在这个区间内遍历查找，而前缀和是通过哈希表的方式使得查找的时间复杂度为O(1)：通过哈希表存放前缀和，然后再去寻找 sum[i]-k 的前缀和，这些操作都是O(1)。
3、为什么往哈希表中插入前缀和元素的操作要放在 count 统计之后呢？这里其实与最上面的 [0, 1]相匹配。可以理解为上面 put(0,1)的操作就是for循环的最开始的一次操作，而后面才开始去 进行count的统计的。即 先插入哈希表，再去统计的逻辑是正确的。
974. 和可被K整除的子数组
题目：
给定一个整数数组nums和一个整数k，返回其中元素之和可被k整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。
示例 1：输入：nums = [4,5,0,-2,-3,1], k = 5 输出：7 解释： 有 7 个子数组满足其元素之和可被 k = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:输入: nums = [5], k = 9 输出: 0
提示:1 <= nums.length <= 3 * 104-104 <= nums[i] <= 1042 <= k <= 104
思路：同样是求子数组，直接先套用双层for循环去暴力求解。
代码实现：
class Solution { public int subarraysDivByK(int[] nums, int k) { // sub_sum % k == 0 // 暴力枚举： int count = 0; for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; if (sum % k == 0) { count++; } } } return count; } }很遗憾，由于这一题的数据量稍微大一些，因此暴力枚举的代码跑不过。
接下来，就得开始优化了。相信有了上一题的铺垫，本题应该很容易能想到 前缀和 的方法，并且可能会觉得是换汤不换药的做法，确实是如此的。
同余定理的介绍：https://baike.baidu.com/item/%E5%90%8C%E4%BD%99%E5%AE%9A%E7%90%86/1212360?fr=aladdin
但是有一个要注意的地方： k 是正数，而 sum[i] 的值 可能会出现负数，因此最终取模后的结果，也可能出现 负数的情况，而为了数据的一致性，因此我们得将其转换为正数。根据同余定理：
(sum+k) % k == sum % k，因此我们可以放心的使用。
代码实现：
class Solution { public int subarraysDivByK(int[] nums, int k) { Map<Integer, Integer> hash = new HashMap<>(); hash.put(0,1); int sum = 0; int count = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; // i位置的前缀和 // 求 sum%k == x%k 的个数 count += hash.getOrDefault((sum%k+k)%k ,0); hash.put((sum%k+k)%k, hash.getOrDefault((sum%k+k)%k ,0)+1); } return count; } }525. 连续数组
题目：
给定一个二进制数组nums, 找到含有相同数量的0和1的最长连续子数组，并返回该子数组的长度。
示例 1:输入: nums = [0,1] 输出: 2 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:输入: nums = [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
提示：1 <= nums.length <= 105nums[i]不是0就是1
思路：子数组的问题，首先想到暴力枚举的方法：固定一个起始位置，再寻找满足条件的结束位置即可。
代码实现：
class Solution { public int findMaxLength(int[] nums) { // 暴力枚举 int len = 0; for (int i = 0; i < nums.length; i++) { int count_0 = 0; int count_1 = 0; int j = i; for (; j < nums.length; j++) { if (nums[j] == 0) { count_0++; } else { count_1++; } if (count_0 == count_1) { // 遍历一次，就统计更新一次 len = Math.max(len, (j-i+1)); // 更新长度要+1 } } } return len; } }很明显，暴力枚举的代码通不过全部的测试用例。 因此我们得优化。这一题同样不能使用滑动窗口算法，因为我们无法根据数组中的数字进行出窗口和进窗口的操作。还是得用到前缀和的优化方法。题目是让我们求出一个子数组，其中0和1的个数是相等的，那么我们可以将0当成-1看待，如果符合子数组的要求，即最终的结果就是0.因此我们只要统计数组中最长的0的长度即可。
代码实现：
class Solution { public int findMaxLength(int[] nums) { // 前缀和优化处理（错误版） int n = nums.length; int[] virtual_nums = new int[n+1]; for(int i = 0; i < n; i++) { int target = nums[i] == 0 ? -1 : 1; virtual_nums[i+1] = virtual_nums[i] + target; } // 从前缀数组的后面开始遍历 for (int i = n; i > 0; i--) { if (virtual_nums[i] == 0) { // 这个位置的0、1数量是相等的 return i; } } return 0; } }上面代码的想法是好的，但是会出现和上面两个题目一样的情况。
因此，还得使用前缀和+哈希表的方法。
class Solution { public int findMaxLength(int[] nums) { // 前缀和优化处理+哈希表 Map<Integer, Integer> hash = new HashMap<>(); hash.put(0, -1); // sum = 0时，x是不存在的，即-1下标 int sum = 0; int len = 0; for (int i = 0; i < nums.length; i++) { int target = nums[i] == 0 ? -1 : 1; sum += target; // 前缀和 // 因为sum=x是目标数组存在的情况，因此判断x是否在哈希表中， // 即判断sum是否存在于哈希表中，如果存在，就比较长度 if (hash.containsKey(sum)) { len = Math.max(len, i-hash.get(sum)); } else { // 不存在就加入哈希表 hash.put(sum, i); } } return len; } }注意：
1、哈希表中存放的是前缀和与对应的结束位置下标。
2、对于有重复的 sum 和 下标，我们只需要存放前面的一对就行了，因为后面sum对应的下标肯定在前面一个下标后边，即最终的长度肯定是小于前面一次求的长度，因此我们可以直接忽略。
3、对于sum[i] = 目标数组的情况，我们得预先处理。对应的 -1 下标存放到哈希表中。
4、长度的计算。
有两种理解方式：1、因为我们前面预先处理了 x 处于 -1位置的情况，因此我们在计算时，就直接可以使用 末位置 - 初位置 即可。2、j 是 x 数组的结束位置，i 是目标数组的结束位置。
1314. 矩阵区域和
题目：
给你一个m x n的矩阵mat和一个整数k，请你返回一个矩阵answer，其中每个answer[i][j]是所有满足下述条件的元素mat[r][c]的和：i - k <= r <= i + k,j - k <= c <= j + k且(r, c)在矩阵内。
示例 1：输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2 输出：[[45,45,45],[45,45,45],[45,45,45]]
提示：m == mat.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100
思路：可能有部分小伙伴和我一样，题目没看懂是啥意思，我们可以尝试去画图理解。其实题目就是让我们填充answer数组，而answer数组的 i、j 对应的值是在原数组中以 i、j 的中心，变长为 k 的矩阵和，且对应的 i、j 要在原数组内部。如下图所示：
其实看到这里，基本上我们可以确定是使用前缀和的思想来写的。
这里的题目是在第一篇文章中的第二个题目，可以去点击最上面的链接。
有了上篇文章的经验之后，这个题目也就比较简单了。
代码实现：
class Solution { public int[][] matrixBlockSum(int[][] mat, int k) { int row = mat.length; // 行 int col = mat[0].length; // 列 // 填充前缀和数组 int[][] v_nums = new int[row+1][col+1]; for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { v_nums[i][j] = v_nums[i-1][j]+v_nums[i][j-1]-v_nums[i-1][j-1]+mat[i-1][j-1]; } } // 填充ans数组 int[][] ans = new int[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { // 这里可以在坐标上面+1，这样公式就不用改了 int x1 = Math.max(0, i-k) + 1; int y1 = Math.max(0, j-k) + 1; int x2 = Math.min(row-1, i+k) + 1; int y2 = Math.min(col-1, j+k) + 1; ans[i][j] = v_nums[x2][y2]-v_nums[x1-1][y2]-v_nums[x2][y1-1]+v_nums[x1-1][y1-1]; } } return ans; } }好啦！本期 前缀和算法专题（2）的学习之旅到此结束啦！我们下一期再一起学习吧！
