优选算法——前缀和

👇作者其它专栏

《数据结构与算法》《算法》《C++起始之路》

前缀和相关题解

1.前缀和

算法思路：

a.先预处理出来一个【前缀和】数组：

        用dp[i]表示：[1,i]区间内所有元素的和，那么dp[i-1]里面存的就是[1,i-1]区间内所有元素的和，那么：可得到递推公式：dp[i]=dp[i-1]+arr[i]；

b.使用前缀和数组，【快速】求出【某一个区间内】所有元素的和：

        当访问的区间是[l,r]时：区间内所有元素的和为：dp[r]-dp[l-r]。

#include <iostream> #include <vector> using namespace std; int main() { int n,q; cin>>n>>q; vector<int> arr(n+1); for(int i=1;i<n+1;i++) cin>>arr[i]; //初始化一个前缀和数组 vector<long long> dp(n+1);//防止溢出 for(int i=1;i<n+1;i++) dp[i]=dp[i-1]+arr[i]; int l,r; while(q--){ cin>>l>>r; cout<<dp[r]-dp[l-1]<<endl; } return 0; } 

2.二维前缀和

算法思路：

类比一维数组的形式，若我们能处理出来从[0,0]位置到[i,j]位置这片区域内所有元素的累加和，就可以在O（1）的时间内，搞定矩阵内任意区域内所有元素的累加和。因此我们接下来仅仅需完成两步即可：

◦第一步：搞出来前缀和矩阵

        这里就要用到一维数组里面的拓展知识，我们要在矩阵的最上面和最左边添加上一行和一列0，这样我们就可以省去非常多的边界条件的处理。处理后的矩阵就想这样：

这样，我们填写前缀和矩阵数组的时候，下标直接从1开始，能大胆使用i-1，j-1位置的值。

注意：dp表与原数组matrix内元素的映射关系：

        i.从dp表到matrix矩阵，横纵坐标减一；

        ii.从martix矩阵到dp表，横纵坐标加一。

前缀和矩阵中sum[i][j]的含义，以及如何递推二维前缀和方程

a.sum[i][j]的含义：

sum[i][j]表示，从[0,0]位置到[i,j]位置这段区域内，所有元素的累加和。对应下图的红色区域：

a.递推方程：

其实这个递推方程非常像我们一起做过求图形面积的题，我们可以将[0,0]位置到[i,j]位置这段区域分解成下面的部分：

sum[i][j]=红+蓝+绿+黄，分析一下这四块区域：

        i.黄色部分最简单，它就是数组中的matrix[i-1][j-1]（注意坐标的映射关系）

        ii.单独的蓝不好求，因为它不是我们定义的状态表示中的区域，同理，单独的绿也是；

        iii.但是若是红+蓝，正好是我们dp数组中sum[i-1][j]的值；

        iv.同理，若是红+绿，正好是我们dp数组中sum[i][j-1]的值；

        v.若把上面求的三个值上加起来，那就是黄+红+蓝+红+绿，发现多算了一块红的面积，因此再单独减去红的面积即可；

        vi.红的面积正好也是符合dp数组的定义的，即sum[i-1][j-]。

综上所述，我们的递推方程就是：

        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+matrix[i-1][j-1]

◦第二步：使用前缀和矩阵

题目中接口提供的参数是原始矩阵的下标，为了避免下标映射错误，这里直接先把下标映射成dp表里面对应的下标：row1++，col1++，row2++，col2++

接下来分析如何使用这个前缀和矩阵，如下图（注意这里的row和col都处理过了，对应的正sum矩阵中的下标）：

对于左上角（row1，col1）、右下角（row2，col2）围成的区域，正好是红色的部分。因此我们要求的就是红色部分的面积，继续分析几个区域：

        i.黄色，直接求出来，就是sum[row1-1,col1-1]（为什么-1，因为要剔除掉row这一行和col这一列，即边界情况）

        ii.绿色，直接求不好求，但是和黄色拼接起来，正好是sum表内sum[row1-1][col2]的数据；

        iii.同理，蓝色不好求，但是蓝+黄=sum[row2][col1-1]；

        iv.再看整个面积，正好是sum[row2][col2]；

        v.那么，红色就=整个面积-黄-绿-蓝，但是绿蓝不好求，我们可以这样减：整个面积-（绿+黄）-（蓝+黄），这样相当于多减去了一个黄，再加上即可

综上所述：红=整个面积-（绿+黄）-（蓝+黄）+黄，从而可得红色区域内的元素总和为：

sum[row2][col2]-sum[row2]]col1-1]-sum[row1-1][col2]+sum[row1-1][col1-1]

#include <iostream> #include <vector> using namespace std; int main() { int n, m, q; cin >> n >> m >> q; vector<vector<int >> arr(n + 1,vector<int>(m+1)); for (int i = 1; i < n + 1; i++) for (int j = 1; j < m + 1; j++) cin >> arr[i][j]; //初始化前缀和数组 vector<vector<long long >> dp(n + 1,vector<long long>(m + 1)); for(int i=1;i<n+1;i++) for(int j=1;j<m+1;j++) dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j]; while(q--){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl; } return 0; }

3.寻找数组的中心下标

算法思路：

从中心下标的定义可知，除中心下标的元素外，该与元素左边的【前缀和】等于该元素右边的【后缀和】。

        ◦因此，我们可以先预处理出来两个数组，一个表示前缀和，另一个后缀和。

        ◦然后，我们可以用一个for循环枚举可能的中心下标，判断每一个位置的【前缀和】以及【后缀和】，若两者相等，就返回当前下标。

class Solution { public: int pivotIndex(vector<int>& nums) { int n=nums.size(); //预处理前缀和及后缀和数组 vector<int> f(n),g(n); for(int i=1;i<n;i++) f[i]=f[i-1]+nums[i-1]; for(int i=n-2;i>=0;i--) g[i]=g[i+1]+nums[i+1]; for(int i=0;i<n;i++) if(g[i]==f[i]) return i; return -1; } };

4. 除了自身以外数组的乘积

算法思路：

注意题目的要求，不能使用除法，并且要再O（N）的时间复杂度内完成该题。那么我们就不能使用暴力的解法，以及求出整个数组的乘积，然后除以单个元素的方法。

继续分析，根据题意，对于每一个位置的最终结果ret[i]，它时由两部分组成的：

        i.nums[0]*nums[1]*nums[2]*…*nums[i-1]

        ii.nums[i+1]*nums[i+2]*…*nums[n-1]

于是，我们可以利用前缀和的思想，使用两个数组f和g，分别处理出来两个信息：

        i.f表示：i位置之前的所有元素，即[0,i-1]区间内所有元素的前缀乘积，

        ii.g表示：i位置之后的所有元素，即[i+1,n-1]区间内所有元素的后追乘积

然后再处理最终结果。

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> f(n,1),g(n,1),ans(n); for(int i=1;i<n;i++) f[i]=f[i-1]*nums[i-1]; for(int i=n-2;i>=0;i--) g[i]=g[i+1]*nums[i+1]; for(int i=0;i<n;i++) ans[i]=g[i]*f[i]; return ans; } };

5.和为 K 的子数组

算法思路：

设i为数组中的任意位置，用sum[i]表示[0,i]区间内所有元素的和。

想知道有多少个【以i为结尾的和为k的子数组】，就要找到有多少个起始位置为x1，x2，x3…使得[x,i]区间内的所有元素的和为k。那么[0,x]区间内的和是不是就是sum[i]-k了。于是问题就变成：

◦找到[0,i-1]区间内，有多少前缀和等于sum[i]-k的即可。

我们不用真的初始化一个前缀和数组，因为我们只关心在i位置之前，有多少个前缀和等于sum[i]-k。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。

class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> hash;//统计前缀和子数组的次数 hash[0]=1; int sum=0,ret=0; for(auto x:nums){ sum+=x; if(hash.count(sum-k)) ret+=hash[sum-k]; hash[sum]++; } return ret; } };

6.和可被 K 整除的子数组

前置知识：

●同余定理

若（a-b）%n==0，那么我们可以得到一个结论：a%n==b%n。即若两个数相减的差能被n整除，那么这两个数对n取模的结果相同。

●C++中负数取模的结果，以及如何修正【负数取模】的结果

        a.C++中关于负数的取模运算，结果是【把负数当成正数，取模后加上一个负号】。

                例：-1%3=-（1%3）=-1

        b.因为有负数，为防止发生【出现负数】的结果，以（a%n+n）%n的形式输出保证为正。

                例：-1%3=（-1%3+3）%3=2

算法思路：

思路与5.和为 K 的子数组 相似

设i为数组中的任意位置，用sum[i]表示[0,i]区间内所有元素的和。

●想知道有多少个【以i为结尾的可被k整除的子数组】，就要找到有多少个起始位置为x1，x2，x3…使得[x,i]区间内的所有元素的和可被k整除。

●设[0,x-1]区间内所有元素之和等于a，[0,i]区间内所有元素的和等于b，可得（b-a）%k==0。

●有同于定理可得，[0,x-1]区间与[0,i]区间内的前缀和同余。于是问题就变成：

        ◦找到在[0,i-1]区间内，有多少前缀和的余数等于sum[i]%k的即可。

我们不用真的初始化一个前缀和数组，因为我们只关心在i位置之前，有多少前缀和等于sum[i]-k。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。

class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int,int> hash; hash[0%k]=1;//0这个数的余数 int sum=0,ret=0; for(auto x:nums){ sum+=x;//算出当前位置的前缀和 int r=(sum%k+k)%k;//修正后的余数 if(hash.count(r)) ret+=hash[r];//统计结果 hash[r]++; } return ret; } };

7.连续数组

算法思路1（暴力）：

枚举所有的子数组，然后判断子数组是否满足要求。

算法思路2（前缀和+哈希表）：

题目意为：

●本题让我们找出一段连续的区间，0和1出现的次数相同。

●若将0记为-1，1记为1，问题就变成了找出一段区间，这段区间的和等于0。

●于是，和5.和为 K 的子数组的思路一样。

设i为数组中的任意位置，用sum[i]表示[0,i]区间内所有元素的和。

想知道最大的【以i为结尾的和为0的子数组】，就要找到从左往右第一个x1使得[x1,i]区间内所有元素的和为0。那么[0,x1-1]区间内的和就是sum[i]。于是：

●找到在[0,i-1]区间内，第一次出现sum[i]的位置即可。

不用真的初始化一个前缀和数组，因为我们只关心在i位置之前，第一个前缀和等于sum[i]的位置。因此，仅需用一个哈希表，一边求当前位置的前缀和，一边记录第一次出现该前缀和的位置。

class Solution { public: int findMaxLength(vector<int>& nums) { unordered_map<int,int> hash; hash[0]=-1;//默认有一个前缀和为0的情况 int sum=0,ret=0; for(int i=0;i<nums.size();i++){ sum+=nums[i]==0?-1:1;//计算当前位置的前缀和 if(hash.count(sum)) ret=max(ret,i-hash[sum]); else hash[sum]=i; } return ret; } };

8.矩阵区域和

算法思路：

左上角坐标：x1=i-k，y1=j-k，但由于会【超过矩阵】的范围，因此需要对0取一个max。因此修正后的坐标为：x1=max（0，i-k），y1=max（0，j-k）：

右下角坐标：x1=i+k，y1=j+k，但是由于会【超过矩阵】的范围，因此需要对m-1，以及n-1取一个min。因此修正后的坐标为：x2=min（m-1，i+k），y2=min（n-1，j+k）。

然后根据二维前缀和的解题思路计算即可。（注意下标的映射关系）

class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { int m=mat.size(),n=mat[0].size(); //预处理一个前缀和数组 vector<vector<int>> dp(m+1,vector<int>(n+1)); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1]; vector<vector<int>> ret(m,vector<int>(n)); for(int i=0;i<m;i++) for(int j=0;j<n;j++){ int x1=max(0,i-k)+1,y1=max(0,j-k)+1; int x2=min(i+k,m-1)+1,y2=min(j+k,n-1)+1; ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]; } return ret; } };