力扣刷题记录（c++）09
目录
974. 和可被 K 整除的子数组
题目描述：
编辑 题目解析：
代码实现：
525. 连续数组
题目描述：
题目解析：
代码实现：
1314. 矩阵区域和
题目描述：
题目解析：
代码实现:
题目描述：
给定一个整数数组
nums和一个整数k，返回其中元素之和可被k整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。
1 <= nums.length <= 3 * 10^4-10^4 <= nums[i] <= 10^42 <= k <= 104
题目解析：
- 这道题与之前那道和为k的子数组特别像，只是条件不一样而已，但是数据规模变大了，所以再使用枚举的方法就会超时。
- 按照我们之前枚举的思路，枚举到一个区间，假如是sum(x,y]，那么需要用sum[y]-sum[x]，那么可以想到如果sum(x,y]可以被k整除，那么sum[y]与sum[x]除k的余数应该是相等的，那么我们就可以用一个哈希表将这个整除结果保存下来，算到sum[y]时，就可以直接取出对应值，并计算出区间长度。
- 由于要求的是最长的子数组，那么对于相同的余数，我们只需要记录最小的那个位置即可。
- 由于负数除k的余数会被计算为负数，所以在计算余数时要稍微处理一下，代码见。
代码实现：
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int n = nums.size();map<int, int> record({{0, 1}});int ans = 0;int sum = 0;for (auto num : nums) {sum += num;int m = (sum % k + k) % k;if (record.count(m))ans += record[m];record[m]++;}return ans;}
};525. 连续数组
题目描述：
给定一个二进制数组
nums, 找到含有相同数量的0和1的最长连续子数组，并返回该子数组的长度。
1 <= nums.length <= 10^5nums[i]不是0就是1
题目解析：
- 这里如果采用前缀和加枚举区间的方法的话，只需要让区间的和等于区间长度的一半就可以，但是数据规模决定了必然会超时。
- 再想想，1的数目与0的数目相同，那么1的数目减去0的数目就是0，假设x[i]是以起始位置为起点，i为结尾的区间1的个数，y[i]是对应0的个数，那么对于(i,j]这个区间，如果符合条件的话，就有：
- x[j] - x[i] - (y[j] - y[i]) = 0；
- 即x[j] - y[j] = x[i] - y[i];
- 那么我们就可以将x[j] - y[j]作为关键值，将对应位置保存起来，方便直接取出即可。
- 同样只需要保存最小位置即可。
代码实现：
class Solution {
public:int findMaxLength(vector<int>& nums) {map<int, int> hash({{0, 0}});int n = nums.size();int sum1 = 0;int sum0 = 0;int ans = 0;for (int i = 0; i < n; i++) {if (nums[i] == 1)sum1++;elsesum0++;if (hash.count(sum1 - sum0)) {ans = max(ans, i + 1 - hash[sum1 - sum0]);}if (!hash.count(sum1 - sum0)) {hash[sum1 - sum0] = i + 1;}}return ans;}
};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)在矩阵内。
题目解析：
-
题目上说的看起来有点复杂，其实就是对于ans[i][j]，返回mat中从i-k到i+k，从j-k到j+k，也就是一个矩阵（如果不符合条件取边界）范围内的数的和。
-
我们可以用一个二维前缀和数组先记录从起始位置到（i，j）这个位置的范围内的所有树的和。
-
至于计算公式，其实是一个dp过程，对于sum[i][j]（注：我们是从左到右，从上到下计算的，这个位置之前的所有值都假设已经计算完毕），我们这样计算：sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i][j]即可（实际代码中我们对sum数组做出优化，但大体公式不变），大家可以结合图来理解：
-
- 然后就是计算ans数组，结合表格解释：
- 我们要计算红色矩阵中的各个数字的和。
- sum[i][j]表示从起始位置开始，我们需要减去一些不必要的，也就是蓝色和绿色还有橙色。
- 如果单纯减去sum[m][j]与sum[i][n]，会导致橙色被减去两次，所以要加回来。
- 公式：ans[i][j] = sum[i][j] - sum[m][j] - sum[i][n] + sum[m][n]
代码实现:
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int n = mat.size();int m = mat[0].size();vector<vector<int>> sums(n + 1, vector<int>(m + 1, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {sums[i + 1][j + 1] =sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + mat[i][j];}}vector<vector<int>> ans(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int r1 = max(0, i - k);int r2 = min(n, i + k + 1);int c1 = max(0, j - k);int c2 = min(m, j + k + 1);ans[i][j] =sums[r2][c2] - sums[r2][c1] - sums[r1][c2] + sums[r1][c1];}}return ans;}
};