目录
编辑
一、前言
二、正文
1. 连续数组
1.1 题目解析
1.2 算法原理
1.3 具体代码
2. 矩阵区域和
2.1 题目解析
2.2 算法原理
2.3 具体代码
三、结语
一、前言
本文将继续为大家带来前缀和的讲解，希望小伙伴们能够从中有所收获！！！
二、正文
1. 连续数组
1. 连续数组 - 力扣（LeetCode）
1.1 题目解析
本题要求我们能够从所给数组中找到含有相同数量的0和1的最长连续子数组，并返回该子数组的长度
1.2 算法原理
本题依旧是采取前缀和加哈希表的方法。不知道小伙伴们还记不得我们在前缀和中讲过一道在数组中找和为k的子数组，由于题目要求我们找到含有相同数量的0和1的最长连续子 数字，如果我们把0换成-1，是不是就转换成了找和为0的最长连续子数组。
代码细节：
①哈希表中存的是前缀和和对应下标，由于本题求的是最长连续子数组，因此我们不再存储前缀和出现的次数，而是前缀和对应的下标
②前缀和存入哈希表的时机依旧是在处理完子数组后存入哈希表
③如果有重复的前缀和，我们只保留最前面的那对，保证求出的是最长的连续子数组
④哈希表先存入前缀和为0，下标为-1,这是为了应对在求最长子数组的时候，从数组起始下标到此时下标就符合题目要求的情况
1.3 具体代码
class Solution {
public:int findMaxLength(vector<int>& nums) {int sum=0,ret=0;unordered_map<int,int> hash;hash[0]=-1; //默认有一个前缀和为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;}
};2. 矩阵区域和
2. 矩阵区域和 - 力扣（LeetCode）
2.1 题目解析
本题要求我们返回一个矩阵，矩阵中每个位置的值为所给矩阵中对应下标拓展k的空间后对应矩阵区域的和，以下图为例，我们要求【0,0】，k=1的矩阵区域和，即以【0,0】为中心的一个3*3矩阵，由于【0,0】处于左上角，所以最后计算的只有四个元素的和。
2.2 算法原理
本题与我们在前缀和（一）中讲过的二维前缀和有点像，都是求一个矩形区域的和，不同的是本题我们需要对矩阵的边界进行处理，避免数组越界的情况。
注：前缀和矩阵应比所给矩阵要多出一行一列，方便对边界的处理，具体细节可跳转至前缀和（一）中的二维前缀和，除此之外，由于我们最后返回的矩阵是比前缀和矩阵少一行一列，因此在求矩阵区域和的时候，需要对x1，x2，y1，y2进行处理。
2.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>> ret(m,vector<int>(n));vector<vector<int>> dp(m+1,vector<int>(n+1));for(int x=1;x<=m;++x)for(int y=1;y<=n;y++)dp[x][y]=dp[x-1][y]+dp[x][y-1]-dp[x-1][y-1]+mat[x-1][y-1];//2. 计算矩阵区域和for(int x=0;x<m;x++)for(int y=0;y<n;y++){int x1=max(0,x-k)+1,x2=min(x+k,m-1)+1;int y1=max(0,y-k)+1,y2=min(y+k,n-1)+1;ret[x][y]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];//交叉}return ret;}
};三、结语
到此为止，本文关于前缀和（四）内容到此结束了，如有不足之处，欢迎小伙伴们指出呀！
关注我 _麦麦_分享更多干货：_麦麦_-CSDN博客
大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！
欢迎大家参观我的算法专栏：麦麦的算法专栏
