【优选算法】前缀和

一、【模板】前缀和

题目描述：

思路讲解：
简单的看过此题后，发现本题有一个暴力解法就是每给出两个下标，就遍历这个数组将这两个数字内的数字相加起来，若每次查询都是将数组从头到尾的相加起来，那么这个解法的时间复杂度就是O(q*n)。

本题还可以使用前缀和的思想来解决，前缀和能够快速求出数组中某一段连续区间的和。

我们仔细看一下题目可以发现题目给出的数组下标是从1开始的，我们这里定义一个同等规模的前缀和数组sum，并将sum[0]置为0，sum[i]记录的是下标为i时，题目给出数组下标1 ~ i所有数的和，通过下图我们可以发现sum[i]=sum[i-1]+arr[i]，想要计算题目给出数组下标l ~ r之间所有数的和，就可以使题目给出数组中下标1 ~ r中所有数之减去下标1 ~ l-1中所有数，也就是sum中r下标的数减去下标为l-1下的数来即是答案也就是sum[r]-sum[l-1]。使用前缀和思想复杂度为，时间复杂度O(q) + 空间复杂度O(n)。至于这里数组为什么要以1开头是因为方便处理边界情况，若开头为0，并且l也为0就会导致越界的情况。

编写代码：

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n = 0 , q = 0;cin >> n >> q;vector<int> v;vector<long long> sum;sum.push_back(0);sum.reserve(n + 1);for(int i = 1 ; i < n + 1 ;i++){int num = 0;cin >> num;sum[i] = sum[i-1] + num;}int l = 0 , r = 0;while(q--){cin >> l >> r;cout << sum[r] - sum[l-1] << endl;}return 0;
}
// 64 位输出请用 printf("%lld")

---

二、【模板】二维前缀和

题目描述：

思路讲解：
本题可以使用暴力解法，将题目给出范围中所有的数遍历相加即可，那么本题的时间复杂度会达到O(q* n *m)，并不是一个很好的方法。

本题可以使用前缀和的思想，定义一个二维前缀和数组dp，并且dp数组第0行和第0列的所有数都置为0，计算出前缀和的结果从第1行和第1列开始向dp中填充，dp[i][j]代表的是题目给出的数组（原数组）中[1，1]到[i，j]范围内所有数之和，通过下图我们发现如果我们想直接求得dp[x][y]也就是A+B+C+D并不好求，但是我们进行简单的转换A+B+C+D=(A+C)+(A+B)+D-A就很好求了，所以求dp[x][y]的公式就是dp[x][y]=dp[x][y-1]+dp[x-1][y]+vv[x][y]-dp[x-1][y-1]。

通过下图我们看出，如果想计算出原数组中[x1，y1]到[x2，y2]范围内所有数之和，使用整块面积(S)-A-B-C可以求得D，但是B和C却不得而知，所以我们可以转换思路，我们知道A，知道A+C，知道A+B，所以可以使用S-(A+C)-(A+B)+A来求得D，所以计算出原数组中[x1，y1]到[x2，y2]范围内所有数之和就可以使用dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]得到答案。上面提到的dp数组第0行和第0列的所有数都置为0，是为了防止上面计算时出现越界的情况。

编写代码：

#include <iostream>
#include <vector>
using namespace std;int main() {int n = 0 , m = 0 , q = 0;vector<vector<int>> vv;vector<vector<long long>> dp;cin >> n >> m >> q;vv.resize(n + 1);dp.resize(n + 1);// 初始化dp二维数组for(int i = 0 ; i < n + 1 ; i++){vv[i].resize(m + 1);dp[i].resize(m + 1);}for(int i = 0 ; i < n + 1 ;i++){vv[i][0] = 0;dp[i][0] = 0;}for(int i = 0 ; i < m + 1 ;i++){vv[0][i] = 0;dp[0][i] = 0;}// 初始化vv二维数组for(int i = 1 ; i < n + 1 ; i++)for(int j = 1 ; j < m + 1 ; j++)cin >> vv[i][j];// 计算补充dp二维数组for(int i = 1 ; i < n + 1 ; i++){for(int j = 1 ; j < m + 1 ; j++){dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + vv[i][j];}}while(q--){int x1 , y1 , x2 , y2;cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;}return 0;
}
// 64 位输出请用 printf("%lld")

---

三、寻找数组的中心下标

题目描述：

思路讲解：
本题可以使用暴力解法，遍历数组的每一个位置，并遍历分别计算当前位置左边和右边所有数的和，从头这样操作有左边数之和等于右边数之和，返回当前位置，若没有找到则返回-1，但是这样操作会使时间复杂度达到O(q*n²)，显然不是一个很好的解法。

这里可以使用前缀和的思想定义两个数组，前缀和数组f，后缀和数组g，f[i]记录的是数组num中下标i-1之前所有数的和，f[i]=f[i-1]+nums[i-1]，g[i]记录的是数组num中下标i+1以后所有数之和，g[i]=g[i+1]+nums[i+1]，做完这些以后，只需要从头遍历数组下标，判断f[i]是否等于g[i]，若相同返回当前下标，一直不相等则返回-1。这里需要注意一下边界问题，当i为0和n-1时，会分别导致数组f和数组g越界，所以我们需要提前对这两个位置做处理，f[0]=0，g[n-1]=0。还需要注意的是f数组需要从左往右开始计算，数组g需要从右向左计算。

编写代码：

class Solution {
public:int pivotIndex(vector<int>& nums) {vector<int> f; // 记录前缀和vector<int> d; // 记录后缀和int numsLen = nums.size();f.reserve(numsLen + 1);d.reserve(numsLen + 1);f[0] = 0 , d[numsLen] = 0 , d[numsLen-1] = 0;// 前缀和记录的是除当前数字外，前面所有数字的和for(int i = 1 ; i <= numsLen ; i++)f[i] = f[i-1] + nums[i-1];// 后缀和记录的是除当前位置外，后面所有数字的和for(int i = numsLen - 2 ; i >= 0 ; i--)d[i] = d[i+1] + nums[i+1];for(int i = 0 ; i < numsLen ;i++){if(f[i] == d[i])return i;}return -1;}
};

---

四、除自身以外数组的乘积

题目描述：

思路讲解：

本题可以使用暴力解法，遍历数组的每一个位置，并遍历并计算除下标i以外当所有数的积，但是这样操作会使时间复杂度达到O(q*n²)，显然不是一个很好的解法。

本题与上一题的思路基本一致，这里可以使用前缀和的思想定义两个数组，前缀和数组f，后缀和数组g，f[i]记录的是数组num中下标i-1之前所有数的积，f[i]=f[i-1]+nums[i-1]，g[i]记录的是数组num中下标i+1以后所有数之积，g[i]=g[i+1]+nums[i+1]，做完这些以后，只需要从头遍历数组下标，每遍历一个下标就将f[i]*g[i]放到对应的ans数组中。这里需要注意一下边界问题，当i为0和n-1时，会分别导致数组f和数组g越界，所以我们需要提前对这两个位置做处理，f[0]=1，g[n-1]=1。还需要注意的是f数组需要从左往右开始计算，数组g需要从右向左计算。

编写代码：

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {vector<int> f; // 记录前缀积vector<int> d; // 记录后缀积vector<int> ans;int numsLen = nums.size();f.reserve(numsLen + 1);d.reserve(numsLen + 1);f[0] = 1 , d[numsLen] = 1 , d[numsLen - 1] = 1;// 除当前位置数字，所有前面所有数字之积for(int i = 1 ; i <= numsLen ; i++)f[i] = f[i-1] * nums[i-1];// 除当前位置数字，所有后面所有数字之积for(int i = numsLen - 2; i >= 0 ;i--)d[i] = d[i+1] * nums[i+1];for(int i = 0 ; i < numsLen ; i++)ans.push_back(f[i] * d[i]);return ans;}
};

---

五、和为 K 的子数组

题目描述：

思路讲解：
本题可以使用暴力解法，遍历出数组num所以的子数组，并得到每个子数组的和，记录和等于k的子数组的个数。这样做会使本题的时间复杂度达到O(n²)，并不是一个很好的方法。

本题可以使用前缀和与哈希表的思想来解决本题，当一个前缀和减去另一个前缀和等于k，就代表着有一段连续的子区间相加等于k，这里定义一个变量sum来代替前缀和数组，sum代表的是num数组中第i位之前（包括第i位）所有数之和，定义一个哈希表unordered_map<int,int> um，um中存储的是第i位之前（不包括第i位）的前缀和的数值和对应出现的次数。

这里有三个点需要注意：

1. 前缀和加入哈希表的时机
   在计算i位置时，哈希表中只存储[0，i-1]位置的前缀和
2. 并不需要真的创建一个前缀和数组
   由于我们哈希表中需要存储的是前缀和和前缀和出现的次数，我们只需要定义一个变量sum，让它来记录当前位置的前缀和，然后再添加到哈希表中即可。
3. 假如整个前缀和数组之和等于k
   我们只需要在最开始的时候在哈希表中添加一个前缀和为0出现过一次即可解决这个问题。由于我最开始sum的值就为0，当um[sum]++;时就处理了这个问题。
   

编写代码：

class Solution {
public:// 以i结尾的前缀和 --> 在i之前sum[i]-kint subarraySum(vector<int>& nums, int k) {unordered_map<int,int> um;int numsLen = nums.size() - 1;int count = 0;int sum = 0;  // 前缀和for(int i = 0 ; i <= numsLen ;i++){// 这里加入的前缀和是前一个位置的前缀和um[sum]++;sum += nums[i];if(um.count(sum-k))count += um[sum - k];}return count;}
};

---

六、和可被 K 整除的子数组

题目描述：

思路讲解：
本题可以使用暴力解法，遍历出数组num所以的子数组，并得到每个子数组的积，记录能整除k的子数组的个数。这样做会使本题的时间复杂度达到O(n²)，并不是一个很好的方法。

本题与上一题的思路有些相似，可以使用前缀和（实际上是前缀积）的思想，在以前学习数学的时候学习过同余定理，我们知道(a - b)/p = k······0 可以推出 a % p == b % p，那么只要两个数（a,b）同时除以另一个数（p）得到的余数相同，那么两数的差一定会被另一个数（p）整除，所以在题目中当两个前缀和除以k得到的余数相同，两个前缀和的差就一定能被k正常，就代表着有一段连续的子区间相加能被k整除，这里定义一个变量sum来代替前缀和数组，sum代表的是num数组中第i位之前（包括第i位）所有数之和，定义一个哈希表unordered_map<int,int> um，um中存储的是第i位之前（不包括第i位）的前缀和对k进行取模得到的数值和对应出现的次数。

这里还有个小细节就是在C /C++中，负数对正数取模得到的数与0相比一定是相等或小于，会导致我们这里的判断出现问题，所以这里要对负数对正数取模得到的数进行修正，我们可以使用(a % p + p)%p对结果进行修正，每个存入哈希表的前缀和都要对k进行取模再进行修正后才能放入哈希表中。

编写代码：

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {// (a - b)/p = k······0   --> a % p == b % p// C++中，负数%正数为负数，负数%正数修正 (a % p + p)%punordered_map<int,int> um;int count = 0;int sum = 0;for(int i = 0 ; i  < nums.size() ; i++){// 前缀和入哈希表um[(sum % k + k) % k]++;sum += nums[i];// sum % k = x % k (x 代表前缀和)if(um.count((sum % k + k) % k))count += um[(sum % k + k) % k];}return count;}
};

---

七、连续数组

题目描述：

思路讲解：
这里使用暴力解法的方式就不做讲解了，也不推荐大家使用暴力解法。

如果这里大家按照题目的思路来做，可能会有点不好解决，但是如果将0该为-1，大家思考一下会不会一下就有思路了。

这里使用前缀和的思想，当下标为i和j位置的前缀和相等那么就代表着原数组在[i，j]这个区间中1和-1的数量是相同的，也就是0和1的数量是相同的。定义一个变量sum，sum代表的是num数组中第i位之前（包括第i位）所有数之和，定义一个哈希表unordered_map<int,int> um，um中存储的是第i位之前（不包括第i位）的前缀和的数值和对应出现的位置的下标。注意题目需要找到含有相同数量的 0 和 1 的最长连续子数组，所以当一个前缀和在哈希表中存在，那么就不需要将其加入哈希表，也不需要修改对应哈希表中的下标。

这里还有两个小细节需要处理一下：

1. 当从下标 i 位置上的前缀和为0
   当数组中没有元素时，前缀和为0，为了处理这种特殊情况，我们需要在哈希表提前加入一组数据{0，-1}。
2. 最长长度的计算方式
   使用当前下标减去哈希表中相同前缀和的下标也就是i - um[sum]。

编写代码：

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> um; // 记录前缀和 和 下标int numsLen = nums.size();;int MaxLen = 0;                    // 记录答案int sum = 0;                       // 前缀和um.insert(make_pair(sum, -1));       // 没元素时，前缀和为0for (int i = 0; i < numsLen; i++){// 将0变为-1if (nums[i] == 0)sum -= 1;elsesum += 1;// 这里需要判断sum是否在um中存在// 否则后面会将sum直接入um，并且second为0if (um.count(sum) != 0 && MaxLen < i - um[sum])MaxLen = i - um[sum];// 由于这里需要最长子数组// 所以这里前缀和相同的下标越小越好// 所以出现过的前缀和后面都不需要入umif (um.count(sum) == 0)um.insert(make_pair(sum, i));}return MaxLen;}
};

---

八、矩阵区域和

题目描述：

思路讲解：
这里使用暴力解法的方式就不做讲解了，也不推荐大家使用暴力解法。

很多人可能但看题目看不出来这题要干什么，以下图为例，i和j是对应需要在ans矩阵中填入答案的下标，k是在下标处向上下左右延展k个位置，将延展后在原数组mat中形成的矩形中所有的数字相加得到的数，填入到数组ans中，需要注意的是越界的位置全部不需要，只需要将有效下标上的数字相加。

本题可以使用前缀和的思想，定义一个二维前缀和数组dp，并且dp数组第0行和第0列的所有数都置为0，计算出前缀和的结果从第1行和第1列开始向dp中填充，dp[i][j]代表的是题目给出的数组（原数组）中[1，1]到[i，j]范围内所有数之和，通过下图我们发现如果我们想直接求得dp[x][y]也就是A+B+C+D并不好求，但是我们进行简单的转换A+B+C+D=(A+C)+(A+B)+D-A就很好求了，需要注意的是dp数组是从第1行第1列开始存储数据的，而原数组mat是从第0行和第0列开始存储数据的，为了让两者的位置对应，所以求dp[x][y]的公式就是dp[x][y]=dp[x][y-1]+dp[x-1][y]+mat[x-1][y-1]-dp[x-1][y-1]。

在本篇文章中的二位前缀和这道题的基础上，我们知道如何使用二位前缀和，只要我们知道所需要的区域的左上角的下标[x1，y1]和右下角的下标[x2，y2]就能解决本道题，x1在i的基础上向上移动k位，y1在j的基础上向左移动k位，x2在i的基础上向下移动k位，y2在j的基础上向右移动k位，但是这两个下标是存在越界的风险的，所以在获取这两个下标时就要做处理，例如坐标小于1就按1处理，大于n就按n处理，这里的1和n是对应着二位前缀和数组的，具体可以看下面代码是如何操作的。想要计算出原数组中[x1，y1]到[x2，y2]范围内所有数之和，看下图我们可以使用整块面积(S)-A-B-C可以求得D，但是B和C却不得而知，所以我们可以转换思路，我们知道A，知道A+C，知道A+B，所以可以使用S-(A+C)-(A+B)+A来求得D，加上我们需要返回的二维数组ans从第0行和第0列开始存储数据的，为了让dp数组与ans数组对应，那么数组ans中元素的计算方式就是，ans[i-1][j-1]=dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]得到答案，这里的i和j也是对应着二位前缀和数组最开始。上面提到的dp数组第0行和第0列的所有数都置为0，是为了防止上面计算时出现越界的情况。

编写代码：

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int n = mat.size() , m = mat[0].size();vector<vector<int>> dp(n + 1 , vector<int>(m + 1));vector<vector<int>> ans(n , vector<int>(m));// 前缀块和for(int i = 1 ; i < n + 1 ;i++){for(int j = 1 ; j < m + 1 ; j++){dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1];}}for(int i = 1 ; i < n + 1 ;i++){for(int j = 1 ; j < m + 1 ; j++){// 防止越界int x1 = max(i-k,1), y1 = max(j-k,1);int x2 = min(i+k,n), y2 = min(j+k,m);// ans的下标与dp下标需要对应ans[i-1][j-1] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];}}return ans;}
};

---

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹