个人主页：沉迷-CSDN博客。
个人专栏：游戏，数据结构，c语言基础，c++学习，算法。
1.什么是前缀和？f;
前缀是指从数组的起始位置到某个位置（或者矩阵的某个区域）所有元素的和。该算法预处理数组或矩阵，计算每个位置（或区域�前缀和，并将其存储在额外的数组或矩阵中c;以便在后续查询中快速获得任何范围（或区域�的和。
一维数组，可采用递推公式。dp[i] = dp[i - 1] + arr[i]。计算前缀和；二维矩阵，类似的递推公式可以使用c;但需要考虑更多的边界情况。接下来，我将用两个问题来详细解释前缀和使用。
二、一维前缀和。
和为k的子数组。
暴力解决方案： 以下标记为0，1... ，nums.size()-1是子数组的左边界依次向右延伸生成子数组。每次延伸都需要判断子数组和是否为k。时间复杂度为O(N^2)代码如下：
class Solution { public: int subarraySum(vector& nums, int k) { int ret=0; for(int i=0;i
xff1前缀和算法a;
如图所示，要使子数组v等于目标值k，必须有sum2-sum1=k，即sum1=sum2-k。然后我们可以在计算过程中计算数组元素的前缀和符合条件的子数组。然后我们可以计算数组元素的前缀，并在计算过程中记录符合条件的子数组。请注意，在计算前缀和过程中需要统计，而非完成所有前缀和计算后的统计。记i=0，我们从下标i到右依次遍历。
需要考虑以下细节：
- 由于这里需要向前搜索前缀，所以为了提高效率，我们将i位置的前缀和结果。累计。在哈希表中，即unordered_map它表示是。
- 在元素存入哈希表之前，需要统计目标子数组的数量，也就是说，前缀从左到右依次计算，然后统计，最后，把前缀放在哈希表里。这样，计数就可以不重不漏地完成。
- 存储前缀和不需要单独创建数组c;但是要方便地记录i位置的前缀和，存储前一个元素（需要一个变量;即i-1）的前缀和。
- 初始化：如果i位置的前缀恰好是k，即sum2-k等于0，说明这个位置下标为0的区间符合条件，需要记录的，但它前面没有一个位置的下标前缀和0，因此，哈希表的前缀和0的位置需要初始化为一次。
class Solution { public: int subarraySum(vector& nums, int k) { unordered_map hash; hash[0]=1;///初始化哈希表 int result=0; int sum=0;//计算前缀和 for(int i=0;i
三、二维前缀和 。
矩阵区域和。
矩阵区域和。
标题是给你一个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]。在dp表中，我们可以使用两层for循环来填充所有位置的前缀。
所以我们如何使用前缀和数组？f;让我们来看看下面面积A的计算。
如果不考虑边界问题，我们可以将随机面积分为四个已知的前缀和小矩阵。以上分解A=S1-S2-S3+S4，而且这些区域已经存储在dp表中，我们只需要找到它们的下标就可以在dp表中找到。所以现在关键是确定他们的下标位置，以下：
A=dp[x2][y2]-dp[x1][y2]-dp[x2][y1]#43];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。
接下来，我们需要打开另一个存储结果的空间c;每个位置按公式使用两个for循环。
dp[i][j]=dp[x2][y2]-dp[x1][y2]-dp[x2][y1]#43];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; }};
