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

1. 连续数组连续数组解题思路暴力O(N^2)枚举所有子数组判断数组内部的01数量是否满足要求。不难发现本题和前几道前缀和题目的要求类似都是在一个数组中找一段区间。如果使用前缀和的方法本题就转化为找出一段和固定的连续区间。由于0在加法中很难体现因此考虑将0看作-1这样题目就变为找一段连续的区间使得这段区间的和为0。于是思路就和上一题查找和为k的子数组很类似了。前缀和哈希表时O(N)空O(N)引入哈希表存储子串的前缀和转化为在数组中查找和为0的区间和。注意点需要留意哈希表下标为0的位置是初始化为-1而不是0因为在思路上我们将0当作-1看待。同时因为求的是最长数组的长度因此哈希表的第二个参数用于存储下标。在遇到重复的sum我们只需保留最早出现sum的下标即可长度最大。classSolution{public:intfindMaxLength(vectorintnums){unordered_mapint,inthash;intnnums.size();intsum0,ret0;hash[0]-1;//下标为-1for(inti0;in;i){sum(nums[i]0?-1:1);if(hash.count(sum)!0){intleni-hash[sum];//注意画图这里不用加1retmax(ret,len);}else{hash[sum]i;}}returnret;}};2. 矩阵区域和矩阵区域和解题思路大致题意是求出数组中每个坐标上下左右扩展k格的区间和并返回新的数组。由于需要连续多次求出二维区间的区间和因此选用前缀和的思想解决。步骤如下step1预处理出一个二维前缀和数组vvstep2创建新数组ret将每个区间和放入数组的对应位置中step3返回ret数组优化点计算前缀和时边界情况的处理很复杂因此我们可以预留第1行和第1列全为0。也就是说mat[i][j]对应的位置为vv[i 1][j 1]。本题关键在于填写ret矩阵时需要找到原矩阵对应区域的左上角和右下角的坐标因此一定要勤于画图classSolution{public:vectorvectorintmatrixBlockSum(vectorvectorintmat,intk){intmmat.size();intnmat[0].size();vectorvectorintvv(m1,vectorint(n1,0));vectorvectorintret(m,vectorint(n));//矩阵和for(inti1;im;i){for(intj1;jn;j){vv[i][j]mat[i-1][j-1]vv[i-1][j]vv[i][j-1]-vv[i-1][j-1];}}for(inti0;im;i){for(intj0;jn;j){intx1(i-k0?0:i-k)1;inty1(j-k0?0:j-k)1;intx2(ikm-1?m-1:ik)1;inty2(jkn-1?n-1:jk)1;intsumvv[x2][y2]-vv[x2][y1-1]-vv[x1-1][y2]vv[x1-1][y1-1];ret[i][j]sum;}}returnret;}};// 本期内容就到这里啦如果对你有帮助请三连支持我是青云我们下期见^_~