【基础算法总结】前缀和

算法原理：

解法1：暴力解法，O(n*q)。就是根据它给的区间，一个一个数加起来，绝对超时。

解法2：前缀和，O(q)+O(n)。
使用前缀和算法的固定流程：
(1) 预处理出来一个前缀和数组
创建一个dp数组，与原数组同规模大小
dp中每个元素 dp[i] 表示：arr数组中 [1,i ] 区间所有元素的和。
可得递推公式：dp[i] = dp[i - 1] + arr[i]

(2) 使用前缀和数组
就是处理每次查询，此时要输入两个数 left 和 right 表示查询区间。
通过分析可以发现：arr 数组里 [left, right] 的区间数据和 = dp[right] - dp[left - 1]。

细节问题：

为什么下标要从1开始？
如果下标从0开始，会出现边界问题 ，根据上面的公式分析：

下标从1开始就是为了处理边界情况。

代码实现：

#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; i++)cin >> arr[i];// 预处理前缀和数组vector<long long> dp(n+1); // 防溢出for(int i = 1; i <= n; i++)dp[i] = dp[i-1] + arr[i];// 使用前缀和数组while(q--){int left, right;cin >> left >> right;cout << dp[right] - dp[left-1] << endl;}
}

算法原理：

解法1：暴力解法，O(n * m * q)。就是根据给的两个坐标，一个一个数加，绝对超时。

解法2：前缀和，O(m * n)+O(q)。
下面的内容将详细介绍前缀和矩阵的处理和使用：

(1) 预处理出一个前缀和矩阵
创建一个前缀和数组dp，大小规模与arr相同。
dp[i][j] 表示：从[1][1] 位置到 [i][j] 位置，这段区间里面所有元素和。
以arr矩阵中的 [i][j] 位置为参考，可以把arr矩阵分成4块：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1]
(2) 使用前缀和矩阵
输入两个查询坐标（x1,y1）和（x2,y2）,输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和。
在arr矩阵中以这两个坐标为参考，可把矩阵分成4块：
子矩阵的和 = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]

细节处理：

参考上一题

代码实现：

#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; i++)for(int j = 1; j <= m; j++)cin >> arr[i][j];// 预处理前缀和矩阵vector<vector<long long>> dp(n+1, vector<long long>(m+1));for(int i = 1; i <= n; i++)for(int j = 1; j <= m; 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;cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] << endl;}
}

算法原理：

解法1：暴力求解，O(N^2)。遍历数组，每次固定一个下标，再分别计算左右两边区间的和，进行比较，绝对超时。

解法2：使用前缀和思想。
(1) 预处理
由于会涉及前后两个区间的求和，所以在预处理时定义一个f表示前缀和数组，g表示后缀和数组：

(2) 使用数组
然后只需要遍历一遍数组，每次固定一个下标，判断 f[i] == g[i] ，如果相等则返回 i，否则返回 -1。

细节问题：

(1) 根据 f 和 g 的递推公式，填 f[0] 时会越界，填 g[n-1] 时，也会越界，所以要先初始化 f[0] = g[n-1] = 0。
(2) 在填dp表时，前缀和数组f从前往后填，后缀和数组g从后往前填。

代码实现：

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

算法原理：

这道题和上一题基本上是一模一样的，也使用前缀和思想，只是本题是算乘法，上一题是算加法。

(1) 预处理
由于会涉及前后两个区间的乘积，所以在预处理时定义一个f表示前缀积数组，g表示后缀积数组：

(2) 使用数组

细节问题：

(1) 根据 f 和 g 的递推公式，填 f[0] 时会越界，填 g[n-1] 时，也会越界，所以要先初始化 f[0] = g[n-1] = 1。
(2) 在填dp表时，前缀和数组f从前往后填，后缀和数组g从后往前填。

代码实现：

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 j = n-2; j >= 0; j--)g[j] = g[j+1] * nums[j+1];// 使用数组vector<int> ret;for(int k = 0; k < n; k++)ret.push_back(f[k] * g[k]);return ret;}
};

算法原理：

我们在 [滑动窗口] 系列中做过一道和本题十分类似的，只不过那道题目中的数据都是正整数，一直累加，结果是单调递增的，所以才可以用 “滑动算法"思想(本质就是"同向双指针”)进行优化。但是这道题中有0和负数，相加的结果不是单调递增的，不能使用 “滑动窗口”。

这道题可以使用：前缀和+哈希表。
我们引入"以 i 位置为结尾的所有的子数组"，如图，所以可以把题目中要求的"和为 k 的子数组"，转化成：在区间 [0, i-1] 中，有多少个前缀和等于 sum[i] - k。
如何快速的统计前缀和个数呢？就要使用哈希表，把每次计算的 sum[i] - k 都扔进哈希表中，同时统计次数。
下图里绿色部分的表示前缀和：

细节问题：

(1) 前缀和加入哈希表的时机。
在计算 i 位置之前，哈希表里面只保存 [0, i-1] 位置的前缀和。
(2) 不用真的创建一个前缀和数组。
用一个变量 sum 来标记前一个位置的前缀和即可。
(3) 如果整个前缀和等于 k 呢？
要在创建哈希表后初始化：hash[0] = 1。就相当于数组默认有一个前缀和为0的子数组。

代码实现：

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;}
};

算法原理：
这道题和上一题太相似了，并且也不能用"滑动窗口"优化，原因同上。

在解决这题之前，先补充两个涉及的知识：
(1) 同余定理：若两数之差整除 p，则这两个数分别对 p 取模，余数相等。

(2) C++中，[负数 % 正数] 的结果以及修正：
在C++中，[负数 %(取模) 正数] 的结果是一个负数，如果想把这个负数修正为正确的正数：

与上一题相同，本题还是使用：前缀和+哈希表
我们也引入"以 i 位置为结尾的所有的子数组"，如图，所以可把本题中要求的"和可被 k 整除的非空子数组的数目"转化为：在 [0, i-1] 区间中，找到有多少个前缀和的余数等于 (sum % k + k) % k 。
如何快速的统计前缀和个数呢？就要使用哈希表。把每次计算的 (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 x : nums){sum += x;int r = (sum % k + k) % k; // 修正后的余数if(hash.count(r) ret += hash[r]; // 统计结果hash[r]++;}return ret;}
};

算法原理：

这道题如果按题目要求直接找相同数量0和1的最长子数组会难度很大。但是如果我们把数组中所有的 0 改成 -1，本题就可以转换成：在数组中，找出最长的子数组，使子数组中所有元素和为0。那它的算法思路就和前文的 [560.和为 k 的子数组] 一模一样了。

转化后，使用：前缀和+哈希表。
具体的算法思路参考 [560.和为 k 的子数组]。

魔鬼细节问题：

(1) 哈希表里存什么？
根据题目要求，存的应该是前缀和的最大长度(下标)。
(2) 什么时候存入哈希表？
和上面一样，在计算 i 位置之前，丢进哈希表。
(3) 如果有重复的 < sum, i>，如何存？
就是在遍历到 i 位置时，发现前面 j 位置的前缀和也等于 sum ，要把两个 sum 都入哈希表吗？不需要，因为要求最大长度。 只保留前面的那一对 < sum, i>

(4) 默认的前缀和为0的情况，如何存？
创建哈希表后，初始化：hash[0] = -1。

(5) 长度怎么算？
因为 [i, j] 是闭区间，计算区间元素是 i - j + 1个，但是这里多算了一个 j 位置，所以还要 -1。

代码实现：

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++){// 计算当前位置前缀和，把 -1 变 0sum += nums[i] == 0 ? -1 : 1; // 如果已经存在了，就不入哈希，更新长度，不存在就入哈希if(hash.count(sum)) ret = max(ret, i - hash[sum]);else hash[sum] = i;}return ret;}
};

算法原理：

先理解题目意思：

很显然，本题要使用二维前缀和。
二维前缀和的预处理矩阵dp的递推公式和使用dp矩阵都在第二题中有详细介绍，这里不再赘述。

细节问题：

代码实现：

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>> ans(m, vector<int>(n));int x1 = 0, y1 = 0, x2 = 0 ,y2 = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){x1 = max(0, i-k) + 1, y1 = max(0, j-k) + 1;x2 = min(i+k, m-1) + 1, y2 = min(j+k, n-1) + 1;ans[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];}}return ans;}
};