【优选算法】前缀和
目录
- 一、[【模板】前缀和](https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196)
- 二、[【模板】二维前缀和](https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196)
- 三、[寻找数组的中心下标](https://leetcode.cn/problems/find-pivot-index/description/)
- 四、[除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/description/)
- 五、[和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/description/)
- 六、[和可被 K 整除的子数组](https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/)
- 七、[连续数组](https://leetcode.cn/problems/contiguous-array/description/)
- 八、[矩阵区域和](https://leetcode.cn/problems/matrix-block-sum/description/)
- 结尾
一、【模板】前缀和
题目描述：
思路讲解：
简单的看过此题后，发现本题有一个暴力解法就是每给出两个下标，就遍历这个数组将这两个数字内的数字相加起来，若每次查询都是将数组从头到尾的相加起来，那么这个解法的时间复杂度就是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*n2)，显然不是一个很好的解法。
这里可以使用前缀和的思想定义两个数组，前缀和数组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*n2)，显然不是一个很好的解法。
本题与上一题的思路基本一致，这里可以使用前缀和的思想定义两个数组，前缀和数组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(n2)，并不是一个很好的方法。
本题可以使用前缀和与哈希表的思想来解决本题，当一个前缀和减去另一个前缀和等于k，就代表着有一段连续的子区间相加等于k，这里定义一个变量sum来代替前缀和数组，sum代表的是num数组中第i位之前（包括第i位）所有数之和，定义一个哈希表unordered_map<int,int> um，um中存储的是第i位之前（不包括第i位）的前缀和的数值和对应出现的次数。
这里有三个点需要注意：
- 前缀和加入哈希表的时机
在计算i位置时，哈希表中只存储[0，i-1]位置的前缀和 - 并不需要真的创建一个前缀和数组
由于我们哈希表中需要存储的是前缀和和前缀和出现的次数，我们只需要定义一个变量sum，让它来记录当前位置的前缀和，然后再添加到哈希表中即可。 - 假如整个前缀和数组之和等于k
我们只需要在最开始的时候在哈希表中添加一个前缀和为0出现过一次即可解决这个问题。由于我最开始sum的值就为0，当um[sum]++;时就处理了这个问题。
编写代码：
class Solution {
public:
// 以i结尾的前缀和 --> 在i之前sum[i]-k
int 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(n2)，并不是一个很好的方法。
本题与上一题的思路有些相似，可以使用前缀和（实际上是前缀积）的思想，在以前学习数学的时候学习过同余定理，我们知道(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)%p
unordered_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 的最长连续子数组，所以当一个前缀和在哈希表中存在，那么就不需要将其加入哈希表，也不需要修改对应哈希表中的下标。
这里还有两个小细节需要处理一下：
- 当从下标 i 位置上的前缀和为0
当数组中没有元素时，前缀和为0，为了处理这种特殊情况，我们需要在哈希表提前加入一组数据{0，-1}。 - 最长长度的计算方式
使用当前下标减去哈希表中相同前缀和的下标也就是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)); // 没元素时，前缀和为0
for (int i = 0; i < numsLen; i++)
{
// 将0变为-1
if (nums[i] == 0)
sum -= 1;
else
sum += 1;
// 这里需要判断sum是否在um中存在
// 否则后面会将sum直接入um，并且second为0
if (um.count(sum) != 0 && MaxLen < i - um[sum])
MaxLen = i - um[sum];
// 由于这里需要最长子数组
// 所以这里前缀和相同的下标越小越好
// 所以出现过的前缀和后面都不需要入um
if (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;
}
};
结尾
如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹
