《算法题讲解指南：优选算法-前缀和》--31.连续数组，32.矩阵区域和
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
31. 连续数组
题目链接：
525. 连续数组 - 力扣（LeetCode）
题目描述：
题目示例：
解法（前缀和+哈希表）：
算法思路：
稍微转换一下题目，就会变成我们熟悉的题：
- 本题让我们找出一段连续的区间，0和1出现的次数相同。
- 如果将0记为-1，1记为1，问题就变成了找出一段区间，这段区间的和等于0。
- 于是，就和之前做过的那个和为 k 的子数组的题思路类似了
设 i 为数组中的任意位置，用 sum[i] 表示【0，i】区间内所有元素的和。
想知道最大的【以 i 结尾的和为 0 的子数组】，就要找到从左往右第一个 x1 使得【x1，i】区间内所有元素的和为 0。那么【0，x1-1】区间内的和是不是就是 sum[ i ] 了。于是问题就变成：
- 找到在【0，i - 1】区间内，第一次出现 sum[ i ] 的位置即可。
我们还是不用真的初始化一个前缀和数组，因为我们只关心 i 位置之前，第一个前缀和等于 sum[ i ] 的位置，因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边记录第一次出现该前缀和的位置。
C++算法代码：
class Solution { public: int findMaxLength(vector<int>& nums) { unordered_map<int, int> hash; int len = 0; int sum = 0; hash[0] = -1; for(int i = 0; i < nums.size(); i++) { if(nums[i] == 0) { nums[i] = -1; } sum += nums[i]; if(hash.count(sum)) { len = max(len, i - hash[sum]); } else //当第一次遇见前缀和则哈希表存放对应的下标(保证长度最短) { //如果是重复遇见相同的前缀和，则只更新长度不存放到哈希表 //因为重复遇见的前缀和长度一定比第一次长，无需存放 hash[sum] = i; } } return len; } };算法总结及流程解析：
32. 矩阵区域和
题目链接：
1314. 矩阵区域和 - 力扣（LeetCode）
题目描述：
题目示例：
解法：
算法思路：
二维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对于区域的【左上角】以及【右下角】的坐标（大家可以画图，我后面的笔记里会有）
- 左上角坐标：x1 = i - k，y1 = j - k，但是由于可能会【超过矩阵】的范围，因此需要对 0 取一个 max。因此修正后的坐标为：x1 = max(0, i - k)，y1 = max(0, j - k)；
- 右下角坐标：x2 = i + k，y2 = j + k，但是由于可能会【超过矩阵】的范围，因此需要对 m-1，以及 n - 1 取一个 min。因此修正后的坐标为：x2 = min(m-1, i+k)，y2 = min(n-1, j+k)。
然后将求出来的坐标代入到【二维前缀和矩阵】的计算公式上即可（但是要注意下标的映射关系）
C++算法代码：
class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { int m = mat.size(); int n = mat[0].size(); vector<vector<int>> sums(m + 1, vector<int>(n + 1, 0)); vector<vector<int>> ret(m, vector<int>(n, 0)); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { sums[i + 1][j + 1] = mat[i][j] + sums[i][j + 1] + sums[i + 1][j] - sums[i][j]; } } for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { //max和min是为了处理越界情况 ret[i][j] = sums[min(m, i + 1 + k)][min(n, j + 1 + k)] - sums[max(0, i - k)][min(n, j + 1 + k)] - sums[min(m, i + 1 + k)][max(0, j - k)] + sums[max(0, i - k)][max(0, j - k)]; //i + 1和j + 1的目的就是为了和mat进行映射关系，sums[i + 1][j + 1] -> mat[i][j] //然后i - k实际上是i + 1 - k - 1，i + 1依然是与mat进行映射关系 } } return ret; } };算法总结及流程解析：
结束语
到此，31.连续数组，32.矩阵区域和 这两道算法题就讲解完了。连续数组 将0/1转换后用前缀和+哈希表寻找和为0的最长子数组；矩阵区域和 通过二维前缀和快速计算矩阵区域和，注意处理边界条件。希望大家能有所收获！
