算法：前缀和

1.【模版】前缀和

【模板】前缀和_牛客题霸_牛客网

这道题如果使用暴力解法时间复杂度为O(n*m)，会超时，所以要使用前缀和算法。

前缀和->快速求出数组中某一个连续区间的和。

第一步：预处理出一个前缀和数组 dp。

        dp[i]表示[1, i] 区间内所有元素的和，dp[i] = dp[i - 1] + arr[i]。

第二步：使用前缀和数组

        要求[l, r] 区间的值，就等于dp[r] - dp[l - 1]。

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n, m;cin >> n >> m;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数组{dp[i] = dp[i - 1] + arr[i];}int left = 0, right = 0;while(m--){cin >>left >> right;cout << dp[right] - dp[left - 1] << endl;}return 0;
}

2.【模版】二维前缀和

【模板】二维前缀和_牛客题霸_牛客网

和上题一样，使用前缀和，定义一个和原二维数组大小相同的dp矩阵，初始化dp矩阵：

使用dp矩阵：

#include <iostream>
#include <vector>
using namespace std;int main() 
{//读入数据int n,m,q;cin>> n >> m >> q;vector<vector<long long>> arr(n + 1, vector<long long>(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] + arr[i][j] -dp[i - 1][j - 1];}}//使用前缀和矩阵int x1,y1,x2,y2;while(q--){cin >> x1 >> y1 >> x2 >> y2;long long ret = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];cout << ret <<endl;}return 0;
}
// 64 位输出请用 printf("%lld")

3.寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣（LeetCode）

 方法一：遍历数组，求出数组的总值total，

当遍历到第 i 个元素时，设其左侧元素之和为 sum，则其右侧元素之和为 total−nums[i]
 −sum。左右侧元素相等即为 sum=total−nums [i] − sum。

方法二：前缀和。

f(n)前缀和数组 f[i]表示[0, i - 1]区间，所有元素的和。f[i] = f[i - 1] + nums[i - 1]。

g(n) 后缀和数组 g[i]表示[i + 1, n - 1]区间，所有元素的和。 g[i] = g[i + 1] + nums[i + 1]。

在遍历数组，找到 i 值 f[i] == g[i]。

细节问题：f[0] = 0,g[n - 1] = 0。f从左向右遍历初始化，g从右向左遍历初始化。

class Solution {
public:int pivotIndex(vector<int>& nums) {/*int total = 0;for(auto e : nums){total += e;}int sum = 0;for(int i = 0; i < nums.size(); i++){ if(sum == total - sum - nums[i]){return i;}sum += nums[i];}return -1;*/int n = nums.size();vector<int> f(n),g(n);//f(n)为前缀和数组，g(n)为后缀和数组for(int i = 1; i < n; i++)//初始化前缀和数组f(n){f[i] = f[i - 1] + nums[i - 1];}for(int i = n - 2; i >= 0; i--)//初始化后缀和数组g(n){g[i] = g[i + 1] + nums[i + 1];}for(int i = 0; i < n; i++){if(f[i] == g[i])return i;}return -1;}
};

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

238. 除自身以外数组的乘积 - 力扣（LeetCode）

前缀积：

预处理前缀积f   f[i]表示[0, i - 1]区间中所以元素的乘积，f[i] = f[i - 1] * nums[i - 1]。

预处理后缀积g  g[i]表示[i + 1,n - 1]区间中所以元素的乘积，g[i] = g[i + 1] * nums[i + 1]。

细节处理：f[0] = 1,g[n - 1] = 1。

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

5.和为k的子数组

560. 和为 K 的子数组 - 力扣（LeetCode）

思路1：暴力枚举 时间复杂度O(N^2)。

这道题不能使用双指针来做优化，因为这个值有负数和零，保证不了区间内的单调性。

思路2：前缀和 + 哈希表

将问题转换成：以i位置为结尾的所有子数组，在[0, i - 1]区间内，有多少个前缀和等于sum[i] - k。

哈希表中存放的是前缀和 和 出现的次数。

细节问题：

1.前缀和加入哈希表的时机 -> 在计算 i 位置之前，哈希表里只保存[0, i - 1]位置的前缀和

2.不需要再创建一个前缀和数组，用一个sum来记录前一个位置的前缀和即可。

3.如果整个前缀和等于 k 让hash[0] = 1。

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 e : nums){sum += e;if(hash.count(sum - k))ret += hash[sum - k];hash[sum]++;}return ret;}
};

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

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

1.同余定理：（a - b）/ p = k ...... 0 --> a % p == b % p

2.c++和java中（负数%正数）的结果还为负数，修正：a % p + p（负数修正为正数但如果是正数就不正确了） -> (a % p + p) % p。

思路：在[0, i - 1]区间内，找到有多少个前缀和的余数等于（sum % k + k）% 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 e : nums){sum += e;int r = (sum % k + k) % k;//余数if(hash.count(r))       ret += hash[r];hash[r]++;}return ret;}
};

7. 连续数组

525. 连续数组 - 力扣（LeetCode）

思路：将所有0修改成 -1 ，转换成在数组中，找出最长的子数组，使子数组中所有元素的和为0。

1.哈希表中存前缀和和下标。

2.什么时候存入哈希表，使用完当前元素后，存入哈希表

3.如果有重复的<sum, i>，只保留前面的那一对<sum, i>

4.前缀和默认为0的情况 ->hash[0] = -1

5.长度为i - j

下述具体思路为liuduo-yu - 力扣（LeetCode）LLL大佬所做非常详细所以我直接拷贝了过来。

* 解题思路:* 本题的意思是找到具有相同数量 0，1 的最长连续子数组，也就是子数组中要同时具有 0 和 1，并且 0 和 1 的数量是相同的, 并且是最长* 的子数组(好像是废话...）。* <p>* 给出一组测试用例：[0,0,0,1,1,1,0,0,1], 用指针 i 扫描一遍数组, 来观察每个位置上的可能情况* [0,0,0,1,1,1,0,0,1]* -i                 不符合条件, 0 1 数量不同* [0,0,0,1,1,1,0,0,1]* -  i               不符合条件, 0 1 数量不同* [0,0,0,1,1,1,0,0,1]* -    i             不符合条件, 0 1 数量不同* [0,0,0,1,1,1,0,0,1]* -      i           此时与前一个 0 构成 [0,1] 满足条件, 此时的子数组长度为 2* [0,0,0,1,1,1,0,0,1]* -        i         此时 [1,4] 区间满足条件, 子数组长度为 4* [0,0,0,1,1,1,0,0,1]* -          i       此时 [0,5] 区间满足条件, 子数组长度为 5* [0,0,0,1,1,1,0,0,1]* -            i     不符合条件* [0,0,0,1,1,1,0,0,1]* -              i   此时 [0,7] 区间满足条件, 子数组长度为 8* [0,0,0,1,1,1,0,0,1]* -                ^ 不符合条件* <p>* 当遍历完整个数组后, 我们可以知到 [0, 7] 区间是符合条件的最长连续子数组。肉眼很容易辨别哪个区间为最长连续子数组, 但是计算机如* 何能知道？答案是计算区间和, 如果让 0 变为 -1, 那么当区间内 -1 和 1 的数量相同时, 这区间和就是 0 。如此, 似乎可以使用前缀和* 来解决这个问题, 当计算的前缀和为 0 时, 就说明[0,i] 区间是满足题目要求的一个子数组。不过这样肯定会出现错误, 因为最终的结果不* 一定是从 0 下标开始子数组。例如这个用例 [0,0,1,0,0,0,1,1], 答案应该是 nums[2,7]区间长度为6的数组, 可以用上面的方式进行计算* 前缀和：* -[0,0,1,0,0,0,1,1]* - i               preSum = -1, (用 -1 替换 0);* -[0,0,1,0,0,0,1,1]* -   i             preSum = -2* -[0,0,1,0,0,0,1,1]* -     i           preSum = -1* -[0,0,1,0,0,0,1,1]* -       i         preSum = -2* -[0,0,1,0,0,0,1,1]* -         i       preSum = -3* -[0,0,1,0,0,0,1,1]* -           i     preSum = -4* -[0,0,1,0,0,0,1,1]* -             i   preSum = -3* -[0,0,1,0,0,0,1,1]* -               i preSum = -2* 观察可以发现, 当前缀和相同时, 前一个 i1 后面一个位置开始一直到 i2 的区间是满足题目要求的子数组, 即 nums[i1+1...i2] 满足题* 目要求, 并且 i2 - i1 = 子数组长度, 所以我们只需要计算出 nums[0...n-1] 每一个位置的前缀和, 一旦发现当前的计算出的前缀和在* 之前已经出现过, 就用当前的索引 i2 - 之前的索引 i1 即可求出本次得到的子数组长度,。因为需要求得的是最长连续子数组，所以应用一* 个变量 maxLength 来保存每一次计算出的子数组长度, 取较大值。也因为, 我们需要保存每一个位置的前缀和, 并且还需要通过前缀和找到* 相应位置的索引, 所以，使用 HashMap 来存放 {前缀和:索引}, 在上面例子中我们通过观察得到了 i2 - i1 = 数组长度, 但是有一个很隐* 蔽的缺陷, 即当整个数组即为答案时, i2 = nums.length - 1, i1 = 0 此时得到的数组长度为 nums.length - 1 这显然是错误的。因此* , 为了避免这个错误, 我们初始将 Map 中添加一对 {前缀和:索引}, 即 put(0,-1), 0代表前一个不存在的元素前缀和为 0, -1 代表不存* 在元素的索引。* 当定义了这些条件后, 我们开始用指针 i 遍历数组nums[0...nums.length - 1] 位置上的每一个元素。* 一、用变量 sum 来纪录[0...i]区间的和:* -   1.当 nums[i] == 0 时, sum += -1* -   2.当 nums[i] == 1 时, sum += 1* 二、接着判断 sum 是否已经存在于 HashMap 中:* -   1. 如果存在, 则取出 sum 所对应的索引 j, 那么 nums[j+1,i] 就是一个满足答案的子区间, 用* -      maxLength = Math.max(maxLengnth, i - j); 来纪录最长子数组。* -   2. 如果不存在, 则将 {sum:i} 存放在 HashMap 中作为纪录。* 当数组遍历完毕时, maxLength 中保存的即为答案数组的长度。* <p>*/

class Solution 
{
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;//hash中存的前缀和和下标hash[0] = -1;//默认有一个前缀和为0的情况int sum = 0, maxsize = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1;if(hash.count(sum))//存在的话更新长度maxsize = max(maxsize, i - hash[sum]);elsehash[sum] = i;}return maxsize;}
};

8.矩形区域和

1314. 矩阵区域和 - 力扣（LeetCode）

开一个二维数组arr行列多加1一个，映射mat的二维前缀和。在处理ret的时候要注意下标映射的关系，如果越界了可以处理一个区取对应的最大值或最小值。

class Solution 
{
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(),n = mat[0].size();vector<vector<int>> arr(m + 1,vector<int>(n + 1));//行列多开一个空间便于映射vector<vector<int>> ret(m,vector<int>(n));for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){arr[i][j] = arr[i - 1][j] + arr[i][j - 1] + mat[i - 1][j - 1] - arr[i - 1][j - 1];}}for(int i = 0; i < m; i++){   for(int j = 0; j < n; j++){int x1 = max(0, i - k) + 1;int x2 = min(m - 1, i + k) + 1;int y1 = max(0, j - k) + 1;int y2 = min(n - 1,j + k) + 1;ret[i][j] = arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1];}}return ret;} 
};