福州百度企业网站seo,品牌营销策划服务,如何制作课程网站模板下载地址,哈尔滨建设网站公司哪家好个人主页#xff1a;敲上瘾-CSDN博客 个人专栏#xff1a;游戏、数据结构、c语言基础、c学习、算法 一、什么是前缀和#xff1f; 前缀和是指从数组的起始位置到某一位置#xff08;或矩阵的某个区域#xff09;的所有元素的和。这种算法通过预处理数组或矩阵#xff0c;… 个人主页敲上瘾-CSDN博客 个人专栏游戏、数据结构、c语言基础、c学习、算法 一、什么是前缀和 前缀和是指从数组的起始位置到某一位置或矩阵的某个区域的所有元素的和。这种算法通过预处理数组或矩阵计算出每个位置或区域的前缀和并将其存储在一个额外的数组或矩阵中以便在后续查询中可以快速获取任意区间或区域的和。 对于一维数组可以使用递推公式dp[i] dp[i - 1] arr[i]来计算前缀和对于二维矩阵可以使用类似的递推公式但需要考虑更多的边界情况。接下来我会用两个题来详细讲解前缀和的使用。
二、一维前缀和
和为k的子数组 暴力解法 分别以下标为0,1... nums.size()-1为子数组的左边界依次往右延伸生成子数组。每次延伸需要判断子数组和是否为k。时间复杂度为O(N^2)代码如下
class Solution {
public:int subarraySum(vectorint nums, int k){int ret0;for(int i0;inums.size();i){int sum0;for(int ji;jnums.size();j){sumnums[j];if(sumk) ret;}}return ret;}
};
前缀和算法 如图要使子数组v的和等于目标值k则一定有sum2-sum1k即有sum1sum2-k。那么我们可以计算一下该数组元素的前缀和并在计算过程中进行满足条件的子数组进行记录。注意这里是需要在计算前缀和的过程中进行统计而不是完成所有前缀和计算后统计。记i0我们从下标i往右依次遍历。
需要考虑一下下面几个细节
因为这里需要往前查找前缀和所以为了提高效率我们把i位置的前缀和结果累计在一个哈希表中即unordered_mapint,int它表示是前缀和w前缀和w出现的次数。需要在元素存入哈希表之前进行统计目标子数组个数也就是从左往右依次计算前缀和然后进行统计最后才把该前缀和放入哈希表。这样可以不重不漏的完成计数。不需要单独再创建数组来储存前缀和但是考虑要方便的记录i位置的前缀和需要一个变量来储存前一个元素即i-1的前缀和。初始化如果i位置的前缀和恰好为k即sum2-k等于0说明该位置到下标为0的这块区间都是满足条件的是需要记录的但是在它前面并没有一个位置的下标前缀和为0所以需要将哈希表的前缀和为0的位置初始化为一次。
class Solution {
public:int subarraySum(vectorint nums, int k){unordered_mapint,int hash;hash[0]1;//初始化哈希表int result0;int sum0;//计算前缀和for(int i0;inums.size();i){sumnums[i];if(hash.count(sum-k))//如果hash表中有sum-k这个元素resulthash[sum-k];//i位置的前缀和累计到哈希表中hash[sum];}return result;}
};
三、二维前缀和
矩阵区域和 题目的意思是给你一个mat矩阵和你需要返回的是一个同等规模的矩阵answer
其中矩阵answer[i][j]记录的是mat矩阵中(ij)位置往四面八方延伸k个元素得到的子矩阵的和。
如下mat矩阵中不同的(ij)位置不同的k延伸得到的矩阵。 这个题如果用暴力解法的话时间复杂度非常地高而且有大量的重复计算因为有重复计算所以可以往前缀和方面考虑。
首先我们可以额外开辟同规模的二维空间记为dp使用dp来储存从(ij)到(00)位置为对角围成的矩阵的前缀和。 如上(ij)位置的前缀和dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i][j]。我们使用两层for循环就可以将所有位置的前缀和填到dp表中。
那么我们如何使用前缀和数组呢我们来看下面面积A的计算。 一块随机的面积若不考虑边界问题我们都可以把它分成四块已知前缀和的小矩阵。如上分解AS1-S2-S3S4而这些面积已经储存在dp表中我们只需要找到它们的下标就能在dp表中找到。所以现在关键的是确定它们的下标位置如下 Adp[x2][y2]-dp[x1][y2]-dp[x2][y1]dp[x1][y1]。
对于一个m*n大小的矩阵的下标的查找
x1i-ky1j-k。边界处理如果x10则dp[x1][y1]和dp[x1][y2]不用参与计算当做0处理。
x2iky2jk。边界处理若x2m则改为x2m-1若y2n则改为y2n-1。
接下来我们就需要再开辟一块空间来储存结果使用两个for循环将每个位置按公式 dp[i][j]dp[x2][y2]-dp[x1][y2]-dp[x2][y1]dp[x1][y1]
计算但要考虑边界情况最后返回该矩阵即可。
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k){int mmat.size(),nmat[0].size();//dp表的创建vectorvectorint dp(mat.size(),vectorint(mat[0].size(),0)); for(int i0;idp.size();i){for(int j0;jdp[0].size();j){int s10,s20,s30;if(i-10) s1dp[i-1][j];if(j-10) s2dp[i][j-1];if(i-10j-10) s3dp[i-1][j-1];dp[i][j]s1s2-s3mat[i][j];}}//dp表的使用vectorvectorint ret(m,vectorint(n,0)); for(int i0;im;i){for(int j0;jn;j){int s10,s20,s30,s40;//初始化面积//坐标计算int x1i-k,y1j-k,x2ik,y2jk;if(x2m) x2m-1;if(y2n) y2n-1;//面积计算s1dp[x2][y2];if(x10) s2dp[x1][y2];if(y10) s3dp[x2][y1];if(x10y10) s4dp[x1][y1];ret[i][j]s1-s2-s2s4;}}return ret;}
};
