【算法系列篇】前缀和-2：https://developer.aliyun.com/article/1430517
5. 和为 k 的子数组
https://leetcode.cn/problems/subarray-sum-equals-k/description/
5.1 题目要求
给你一个整数数组 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) { } }
5.2 做题思路
还是先来看看暴力解法是怎样解决的？遍历数组，以数组的每一元素为起始位置，然后看以该元素为起始位置的子数组是否和为 k ，暴力解法的时间复杂度为 O(N*2)。
很多人看到这个题目首先想到的可能是 滑动窗口 ，但是我们需要仔细看题目，使用滑动窗口，需要保证窗口具有单调性，这里题目没有说数组全为非负数或者非整数，所以不能保证窗口的单调性，不能使用滑动窗口。
换个思路，它既然求的是和为 k 的子数组，我们仍然可以使用前缀和的思想，在数组的某个位置之前找到 该位置的前缀和 - k = 该位置之前的某一位置的前缀和，并且这个题目求的是 子数组的个数，我们可以配合着哈希表来进行计数。哈希表中存储的是某一位置的前缀和以及该前缀和出现的次数。
与暴力解法的思路有些许的区别，在构建前缀和数组的时候，我们不以数组中每个元素作为起始位置，而是将每个元素作为结束位置，这样更贴合我们的前缀和思想。
5.3 Java代码实现
class Solution { public int subarraySum(int[] nums, int k) { Map<Integer,Integer> map = new HashMap<>(); //为了防止从0开始到某一位置的子数组的和为k，所以提前放入一个前缀和为0的键值对 map.put(0,1); int n = nums.length; int ret = 0,sum = 0; for(int i = 0; i < n; i++) { sum += nums[i]; ret += map.getOrDefault(sum-k,0); map.put(sum,map.getOrDefault(sum,0) + 1); } return ret; } }
6.和可被 k 整除的子数组
https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
6.1 题目要求
给定一个整数数组 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] <= 104
- 2 <= k <= 104
class Solution { public int subarraysDivByK(int[] nums, int k) { } }
6.2 做题思路
在做这个题目之前，我们需要知道两个额外的知识点：
- 同余定理
如果 (a - b) % n == 0 ，那么我们可以得到⼀个结论： a % n == b % n 。⽤⽂字叙述就是，如果两个数相减的差能被n整除，那么这两个数对n取模的结果相同。
- 在c++和Java中对负数取模的话，结果会是一个负数，所以需要修正负数取模的结果 (a % n + n) % n（a为负数）
当知道这两个定理之后，那么这个题目的思路就跟上面的 和为 k 的子数组 思路是类似的。
6.3 Java代码实现
class Solution { public int subarraysDivByK(int[] nums, int k) { Map<Integer,Integer> map = new HashMap<>(); //同样为了防止从0开始到某一位置的子数组的乘积都能被k整除 map.put(0 % k,1); int n = nums.length; int sum = 0,ret = 0; for(int i = 0; i < n; i++) { sum += nums[i]; int r = (sum % k + k) % k; ret += map.getOrDefault(r,0); map.put(r,map.getOrDefault(r,0) + 1); } return ret; } }
7.连续数组
https://leetcode.cn/problems/contiguous-array/description/
7.1 题目要求
给定一个二进制数组 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 <= 105
- nums[i] 不是 0 就是 1
class Solution { public int findMaxLength(int[] nums) { } }
7.2 做题思路
因为数组中只有二进制数，也就是0和1，我们可以将0当成是-1，当子数组中0和1的数量相同的时候，子数组的和为0。所以这个题目也就相当于求长度最长的和为0的子数组。所以我们哈希表中存储的就是前缀和以及数组的下标。
7.3 Java代码实现
class Solution { public int findMaxLength(int[] nums) { Map<Integer,Integer> map = new HashMap<>(); map.put(0,-1); int n = nums.length; int ret = 0,sum = 0; for(int i = 0; i < n; i++) { sum += (nums[i] == 0 ? -1 : 1); if(map.containsKey(sum)) ret = Math.max(ret,i-map.getOrDefault(sum,0)); else map.put(sum,i); } return ret; } }
8.矩阵区域和
https://leetcode.cn/problems/matrix-block-sum/description/
8.1 题目要求
给你一个 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.length
- n == mat[i].length
- 1 <= m, n, k <= 100
- 1 <= mat[i][j] <= 100
class Solution { public int[][] matrixBlockSum(int[][] mat, int k) { } }
8.3 做题思路
这个题目跟上面的【模板】二维前缀和是类似的，只是这个题目需要我们找到对应的矩阵。
需要注意的是，题目中的 r 和 c 都是从0开始的，也就是说，可能会出现数组越界的情况，这道题题目的重点就是需要处理下标越界的情况。那么如何处理下标越界的情况呢？很简单，前面的不是有从下标1开始的吗？当我们构建前缀和数组的时候，我们也可以将数组下标以1开始，然后在最终结果的数组中填入数据的时候注意下标的映射关系就行了。
8.3 Java代码实现
class Solution { public int[][] matrixBlockSum(int[][] mat, int k) { int n = mat.length; int m = mat[0].length; int[][] dp = new int[n + 1][m + 1]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1]; } } int[][] ret = new int[n][m]; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { //处理下标越界问题，并且解决了下标的映射关系 int x1 = Math.max(0,i-k) + 1,y1 = Math.max(0,j - k) + 1; int x2 = Math.min(n - 1,i + k) + 1,y2 = Math.min(m - 1,j + k) + 1; ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]; } } return ret; } }
总结
通过前缀和算法，我们可以在O(1)的时间复杂度内计算出任意区间的元素和。这在处理大规模数据时非常有用，可以大大提高计算效率。
总结起来，前缀和算法是一种高效计算数组区间和的方法。它通过计算数组的前缀和，可以在O(1)的时间复杂度内得到任意区间的元素和。在实际应用中，前缀和算法经常用于解决数组区间和相关的问题，例如子数组的最大和、子数组的平均值等。通过掌握前缀和算法，我们可以更加高效地解决这类问题。
