当前位置：首页 > news >正文

[LC优选算法#19] 前缀和 | 连续数组 | 矩阵区域和

news 2026/7/9 10:20:06

1. 连续数组

连续数组

解题思路：

暴力O(N^2)：枚举所有子数组，判断数组内部的0，1数量是否满足要求。

不难发现，本题和前几道前缀和题目的要求类似，都是在一个数组中找一段区间。如果使用前缀和的方法，本题就转化为找出一段和固定的连续区间。由于0在加法中很难体现，因此考虑将0看作-1，这样题目就变为：找一段连续的区间，使得这段区间的和为0。于是，思路就和上一题查找和为k的子数组很类似了。

前缀和+哈希表时O(N)空O(N)：引入哈希表存储子串的前缀和，转化为在数组中查找和为0的区间和。

注意点：需要留意哈希表下标为0的位置是初始化为-1而不是0，因为在思路上我们将0当作-1看待。同时，因为求的是最长数组的长度，因此哈希表的第二个参数用于存储下标。在遇到重复的sum，我们只需保留最早出现sum的下标即可（长度最大）。

classSolution{public:intfindMaxLength(vector<int>&nums){unordered_map<int,int>hash;intn=nums.size();intsum=0,ret=0;hash[0]=-1;//下标为-1for(inti=0;i<n;i++){sum+=(nums[i]==0?-1:1);if(hash.count(sum)!=0){intlen=i-hash[sum];//注意画图，这里不用加1ret=max(ret,len);}else{hash[sum]=i;}}returnret;}};

2. 矩阵区域和

矩阵区域和

解题思路：
大致题意是求出数组中每个坐标上下左右扩展k格的区间和，并返回新的数组。由于需要连续多次求出二维区间的区间和，因此选用前缀和的思想解决。步骤如下：

step1：预处理出一个二维前缀和数组vv
step2：创建新数组ret，将每个区间和放入数组的对应位置中
step3：返回ret数组

优化点：计算前缀和时，边界情况的处理很复杂，因此我们可以预留第1行和第1列全为0。也就是说mat[i][j]对应的位置为vv[i + 1][j + 1]。

本题关键在于：填写ret矩阵时，需要找到原矩阵对应区域的左上角和右下角的坐标，因此一定要勤于画图！！

classSolution{public:vector<vector<int>>matrixBlockSum(vector<vector<int>>&mat,intk){intm=mat.size();intn=mat[0].size();vector<vector<int>>vv(m+1,vector<int>(n+1,0));vector<vector<int>>ret(m,vector<int>(n));//矩阵和for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){vv[i][j]=mat[i-1][j-1]+vv[i-1][j]+vv[i][j-1]-vv[i-1][j-1];}}for(inti=0;i<m;i++){for(intj=0;j<n;j++){intx1=(i-k<0?0:i-k)+1;inty1=(j-k<0?0:j-k)+1;intx2=(i+k>m-1?m-1:i+k)+1;inty2=(j+k>n-1?n-1:j+k)+1;intsum=vv[x2][y2]-vv[x2][y1-1]-vv[x1-1][y2]+vv[x1-1][y1-1];ret[i][j]=sum;}}returnret;}};