刷题训练之前缀和（上） https://developer.aliyun.com/article/1565744
🌙topic-->5
题目链接：5.前缀和
题目分析：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
算法原理：
- 解法一：
暴力遍历一维数组，定住一个元素向后寻找，时间复杂度为 O(n*n) ，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用一维前缀和的算法原理：
代码演示：
class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> hash;// 统计前缀和出现的个数 hash[0] = 1;// 处理边界问题 int sum = 0,ret = 0; // 循环 for(auto x : nums) { sum = sum + x;// 累计起来 if(hash.count(sum - k)) // 模拟指针向后移 ret = ret + hash[sum - k]; hash[sum]++; } return ret; } };
🌙topic-->6
题目链接：6.前缀和
题目分析：
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
子数组 是数组的 连续 部分。
算法原理：
- 解法一：
暴力遍历一维数组，定住一个元素向后寻找，时间复杂度为 O(n*n) ，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用一维前缀和的算法原理：
代码演示：
class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int, int> hash; hash[0 % k] = 1; // 0 这个数的余数 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; } };
topic-->7
题目链接：7.前缀和
题目分析：
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
nums[i]不是0就是1
算法原理：
- 解法一：
暴力遍历一维数组，定住一个元素向后寻找，时间复杂度为 O(n*n) ，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用一维前缀和的算法原理：
代码演示：
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++) { sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和 if (hash.count(sum)) ret = max(ret, i - hash[sum]); else hash[sum] = i; } return ret; } };
🌙topic-->8
题目链接：8.前缀和
题目分析：
给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和。
算法原理：
- 解法一：
暴力遍历二维数组，定住一个元素向后寻找，时间复杂度为 O(n*n) ，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用二维前缀和的算法原理：（和第二题相似）
代码演示：
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)); // 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, 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[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]; } return ret; } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
