我爱学算法之—— 前缀和（下）
一、974. 和可被 K 整除的子数组
题目解析
对于这道题，给定一个数组
nums和一个整数k；让我们求在nums中能被k整除的子数组的个数。
算法思路
暴力解法：
枚举出所有的子数组，依次判断和是否能被k整除，并统计数量。
优化：
这道题和560. 和为 K 的子数组思路类似：
枚举子数组时还是遍历以i位置为结束位置的所有子数组。
当遍历到
i位置时，知道前缀和[0,i]区间，要找出以i位置为结束位置的所有能被k整除的子数组的和；而这一段子数组
[j,i]的和等于区间[0, i ]的和减去[0,j-1]的和；也就是前缀和相减；
那如何判断子数组的和能否被k整除，统计次数呢？（依次判断时间复杂度就和暴力解法一样了）
统计以
i位置为结尾的子数组中，满足条件的个数这里只要求出满足条件的个数即可；
同余定理：如果a%k = b%k，则(a-b) % k = 0
要判断子数组的和是否被
k整除，要是判断前缀和sum1减前缀和sum2是否能被k整除；所以，只要保证两段前缀和对k取余的结果是相等的，则该子数组的和就能够被k整除。
所以，在遍历到i位置时，区间[0,i]前缀和对k取余的结果为r，只需要知道前面的所有前缀和中，对k取余的结果为r的数量即可。
所以，只需要统计在i位置之前前缀和对k取余的结果，以及次数即可；（使用hash表统计）
注意：数据范围是存在负数的，而负数对整除取余的结果是负数，所以要进行处理：
(s % k + k) %k取余操作注意：使用
hash表统计时，初始情况下，hash表中要存在hash[0] = 1。
代码实现
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int sum = 0, ret = 0;unordered_map<int, int> hash;hash[0] = 1;for (auto& e : nums) {sum += e;int r = (sum % k + k) % k;if (hash.count(r))ret += hash[r];hash[r]++;}return ret;}
};
二、525. 连续数组
题目解析
题目给定一个数组
nums，其中nums[i]不是0就是1。我们要找到含有相同数量的
0和1的子数组，并且返回该子数组的长度。
算法思路
对于这道题，如果直接去找含有相同数量的0和1的，去统计0和1的次数，可以说还是有一定难度的；
但是换一种思路：将数组nums中所有的0变成1，这样满足条件的子数组（0和1数量相等）的和就变成了0；所以，要找0和1相等的子数组就变成了和为0的子数组。
在数组nums中，找和为0的最长子数组，就和找和为k的子数组思路类似了。
首先，遍历
nums，在遍历到i位置时，区间[0,i]的和为sum，在[0,i-1]中找和前缀和为sum的区间。这样要求的是满足条件的最长子数组的长度，所有使用
hash表记录的是前缀和以及，前缀和[0,j]对应下标j的最小值。最后，在循环判断时，如果区间
[0,i-1]前缀和中存在sum，就判断当前子数组长度是否大于ret，更新结果；如果不存在，就将前缀和sum和对应的下标放入hash表中。
注意：这里hash表中记录的是前缀和，以及对应下标的最小值；所以初识情况下hash表中存在0，且hash[0] = -1。
在遍历到i位置且区间[0, i-1]所有前缀和中存在sum，此时以i位置为结尾满足条件的最长子数组的长度：i - hash[sum]。
代码实现
class Solution {
public:int findMaxLength(vector<int>& nums) {int n = nums.size();for (auto& e : nums) {if (e == 0)e = -1;}int ret = 0, sum = 0;unordered_map<int, int> hash;hash[0] = -1;for (int i = 0; i < n; i++) {sum += nums[i];if (hash.count(sum))ret = max(ret, i - hash[sum]);elsehash[sum] = i;}return ret;}
};
三、1314. 矩阵区域和
题目解析
这道题，给定一个
m*n的矩阵nums和一个整数k，让我们返回一个矩阵answer；其中
answer[i]是nums中满足条件的nums[r][c]的和；（i-k <= r <= i+k、j-k <= c <= j+k）简单来说就是
nums中，子矩阵中所有数的和。
算法思路
这道题总体来说还是比较简单的，我们只需要预处理一个二维前缀和。
对于answer[i][j]，就等于nums中，[i-k][j-k]左上角，[i+k][j+k]右下角子矩阵中所有元素的和；
注意：这里i-k和j-k是可能越界（<0）时要进行判断；同理i+k和j+k也是可能越界的，也要进行判断。
代码实现
class Solution {int dp[110][110];
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();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];}}vector<vector<int>> ret(m, vector<int>(n, 0));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;ret[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] +dp[x1 - 1][y1 - 1];}}return ret;}
};