★ 算法OJ题 ★ 前缀和算法（下）
Ciallo～(∠・ω< )⌒☆ ~ 今天，将继续和大家一起做几道前缀和算法题 ~
❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️
澄岚主页：椎名澄嵐-ZEEKLOG博客
算法专栏：★ 优选算法100天 ★_椎名澄嵐的博客-ZEEKLOG博客
❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️
目录
壹 和为k的子数组
1.1 题目
https://leetcode.cn/problems/subarray-sum-equals-k/description/
1.2 算法解析
1.3 撰写代码
class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int , int> hash; // 记录前缀和出现次数 hash[0] = 1; int sum = 0, ret = 0; // sum记录前缀和 for (auto x : nums) { sum += x; // 计算当前位置的前缀和 if (hash.count(sum - k)) // 统计等于(sum[i] - k)个数 ret += hash[sum - k]; hash[sum]++; // 和为sum的前缀和次数++ } return ret; } };
贰 和可被K整除的子数组
2.1 题目
974. 和可被 K 整除的子数组 - 力扣（LeetCode）
2.2 算法解析
2.3 撰写代码
class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int, int> hash; hash[0 % k] = 1; int sum = 0, ret = 0; for (auto x : nums) { sum += x; // 算出当前位置的前缀和 int r = (sum % k + k) % k; // 修正后的余数 if (hash.count(r)) ret += hash[r]; // 统计结果 hash[r]++; } return ret; } };
叁 连续数组
3.1 题目
3.2 算法解析
3.3 撰写代码
class Solution { public: int findMaxLength(vector<int>& nums) { unordered_map<int, int> hash; hash[0] = -1; // 默认有⼀个前缀和为 0 的情况 int sum = 0, ret = 0; for (int i = 0; i < nums.size(); i++) { int tmp = (nums[i] == 0 ? -1 : 1); // 计算当前位置的前缀和 sum += tmp; // 算出前缀和 if (hash.count(sum)) // 前面有同样的sum ret = max(ret, i - hash[sum]); // 算距离i - j else hash[sum] = i; // 前面没有同样的sum则更新下标 } return ret; } };
肆 矩阵区域和
4.1 题目
4.2 算法解析
4.3 撰写代码
class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { int m = mat.size(), n = mat[0].size(); // 1.预处理一个前缀和矩阵 vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1]; // 2.使用前缀和矩阵 vector<vector<int>> ret(m, vector<int>(n)); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { int x1 = max(0, i - k) + 1; int y1 = max(0, j - k) + 1; int x2 = min(m - 1, i + k) + 1; int y2 = min(n - 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; } };
完
