算法4：前缀和（下）
文章目录
- 和为K的子数组
- 和可被k整除的子数组
- 连续数组
- 矩阵区域和
一定要看懂算法原理之后写代码，博主大概率因注意力不够，看了好多遍，才看懂原理细节。
切记，不彻底懂原理，千万别看代码
和为K的子数组
class Solution {
public:int subarraySum(vector<int>& nums, int k) {int ans = 0;int n = nums.size();unordered_map<int, int> hash;int sum = 0;hash[sum]++;//整个前缀和为Kfor(int i = 0; i < n; ++i){sum += nums[i];//ans += hash[sum - k];if(hash.count(sum - k)) ans += hash[sum - k]; // 小优化hash[sum]++;} return ans;}
};
和可被k整除的子数组
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int ans = 0;int sum = 0;unordered_map<int, int> hash;hash[sum]++;for (auto& e : nums) {sum += e;int r = (sum % k + k) % k;if (hash.count(r))ans += hash[r];hash[r]++;}return ans;}
};连续数组
class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash;int sum = 0;hash[sum] = -1;int ans = 0;for (int i = 0; i < nums.size(); ++i) {sum += nums[i] == 0 ? -1 : 1;if (hash.count(sum))ans = max(ans, i - hash[sum]);elsehash[sum] = i;}return ans;}
};
矩阵区域和
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));vector<vector<int>> arr(m, vector<int>(n));for (int i = 1; i < m + 1; ++i) {for (int j = 1; j < n + 1; ++j) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] +mat[i - 1][j - 1];}}for (int i = 1; i < m + 1; ++i) {for (int j = 1; j < n + 1; ++j) {int up = max(i - k - 1, 0), down = min(m, i + k);int left = max(j - k - 1, 0), right = min(n, j + k);arr[i - 1][j - 1] = dp[down][right] - dp[up][right] -dp[down][left] +dp[up][left];}}return arr;}
};