我爱学算法之—— 前缀和（下）

一、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]); else hash[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; }};