前缀和算法——优选算法

个人主页：敲上瘾-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(vector<int>& nums, int k){int ret=0;for(int i=0;i<nums.size();i++){int sum=0;for(int j=i;j<nums.size();j++){sum+=nums[j];if(sum==k) ret++;}}return ret;}
};

前缀和算法：

        如图要使子数组v的和等于目标值k则一定有sum2-sum1=k，即有sum1=sum2-k。那么我们可以计算一下该数组元素的前缀和并在计算过程中进行满足条件的子数组进行记录。注意这里是需要在计算前缀和的过程中进行统计，而不是完成所有前缀和计算后统计。记i=0，我们从下标i往右依次遍历。

需要考虑一下下面几个细节：

• 因为这里需要往前查找前缀和所以为了提高效率，我们把i位置的前缀和结果累计在一个哈希表中，即unordered_map<int,int>它表示是<前缀和w，前缀和w出现的次数>。
• 需要在元素存入哈希表之前进行统计目标子数组个数，也就是从左往右依次计算前缀和然后进行统计，最后才把该前缀和放入哈希表。这样可以不重不漏的完成计数。
• 不需要单独再创建数组来储存前缀和，但是考虑要方便的记录i位置的前缀和，需要一个变量来储存前一个元素（即i-1）的前缀和。
• 初始化：如果i位置的前缀和恰好为k，即sum2-k等于0，说明该位置到下标为0的这块区间都是满足条件的，是需要记录的，但是在它前面并没有一个位置的下标前缀和为0，所以需要将哈希表的前缀和为0的位置初始化为一次。

class Solution {
public:int subarraySum(vector<int>& nums, int k){unordered_map<int,int> hash;hash[0]=1;//初始化哈希表int result=0;int sum=0;//计算前缀和for(int i=0;i<nums.size();i++){sum+=nums[i];if(hash.count(sum-k))//如果hash表中有sum-k这个元素result+=hash[sum-k];//i位置的前缀和累计到哈希表中hash[sum]++;}return result;}
};

三、二维前缀和 

矩阵区域和

题目的意思是给你一个mat矩阵和，你需要返回的是一个同等规模的矩阵answer

其中矩阵answer[i][j]记录的是mat矩阵中(i，j)位置往四面八方延伸k个元素得到的子矩阵的和。

如下mat矩阵中不同的(i，j)位置，不同的k延伸得到的矩阵。

        这个题如果用暴力解法的话时间复杂度非常地高，而且有大量的重复计算，因为有重复计算所以可以往前缀和方面考虑。

首先我们可以额外开辟同规模的二维空间，记为dp，使用dp来储存从(i，j)到(0，0)位置为对角围成的矩阵的前缀和。

        如上(i，j)位置的前缀和dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i][j]。我们使用两层for循环就可以将所有位置的前缀和填到dp表中。

那么我们如何使用前缀和数组呢？我们来看下面面积A的计算。

        一块随机的面积若不考虑边界问题我们都可以把它分成四块已知前缀和的小矩阵。如上分解A=S1-S2-S3+S4，而这些面积已经储存在dp表中我们只需要找到它们的下标就能在dp表中找到。所以现在关键的是确定它们的下标位置，如下：

A=dp[x2][y2]-dp[x1][y2]-dp[x2][y1]+dp[x1][y1]。

对于一个m*n大小的矩阵的下标的查找：

x1=i-k，y1=j-k。边界处理：如果x1<0则dp[x1][y1]和dp[x1][y2]不用参与计算当做0处理。

x2=i+k，y2=j+k。边界处理：若x2>=m，则改为x2=m-1，若y2>=n则改为y2=n-1。

接下来我们就需要再开辟一块空间来储存结果，使用两个for循环将每个位置按公式

                dp[i][j]=dp[x2][y2]-dp[x1][y2]-dp[x2][y1]+dp[x1][y1]

计算，但要考虑边界情况，最后返回该矩阵即可。

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k){int m=mat.size(),n=mat[0].size();//dp表的创建vector<vector<int>> dp(mat.size(),vector<int>(mat[0].size(),0)); for(int i=0;i<dp.size();i++){for(int j=0;j<dp[0].size();j++){int s1=0,s2=0,s3=0;if(i-1>=0) s1=dp[i-1][j];if(j-1>=0) s2=dp[i][j-1];if(i-1>=0&&j-1>=0) s3=dp[i-1][j-1];dp[i][j]=s1+s2-s3+mat[i][j];}}//dp表的使用vector<vector<int>> ret(m,vector<int>(n,0)); for(int i=0;i<m;i++){for(int j=0;j<n;j++){int s1=0,s2=0,s3=0,s4=0;//初始化面积//坐标计算int x1=i-k,y1=j-k,x2=i+k,y2=j+k;if(x2>=m) x2=m-1;if(y2>=n) y2=n-1;//面积计算s1=dp[x2][y2];if(x1>=0) s2=dp[x1][y2];if(y1>=0) s3=dp[x2][y1];if(x1>=0&&y1>=0) s4=dp[x1][y1];ret[i][j]=s1-s2-s2+s4;}}return ret;}
};