算法专题(四)：前缀和

目录

刷题汇总：传送门！

一、【模板】前缀和

1.1 题目

1.2 思路

1.3 代码实现

二、【模板】二维前缀和

2.1 题目

2.2 思路

2.3 代码实现

三、寻找数组的中心下标 

3.1 题目

3.2 思路

3.3 代码实现

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

4.1 题目

4.2 思路

4.3 代码实现

五、和为 K 的子数组

5.1 题目

5.2 思路

5.3 思路

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

6.1 题目

6.2 思路

6.3 代码实现

七、 连续数组

7.1 题目

7.2 思路

7.3 代码实现

八、 矩阵区域和

8.1 题目

8.2 思路

8.3 代码实现

---

每道题的标题，均是该题目的传送门，点击传送到对应题目！

一、【模板】前缀和 1.1 题目

1.2 思路

暴力求解（模拟）：q次询问，每次将需要的地方加起来返回就好，时间复杂度O(N*q)

前缀和（快速求出数组中某一连续空间的和）：

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 - 1] 。

时间复杂度：O(q)+O(N)

1.3 代码实现

我们的前缀和数组再相加的时候有可能溢出，所以使用long / long long

#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> dp(n+1); for(int i = 1;i <= n;i++) dp[i] = dp[i-1]+arr[i]; //使用前缀和数组 int l=0,r=0; while(q--) { cin >>l >> r; cout << dp[r]-dp[l-1] <<endl; } return 0; }

二、【模板】二维前缀和 2.1 题目

2.2 思路

类比于一维数组的形式，如果我们能处理出来从 [0, 0] 位置到 [i, j] 位置这片区域内所有元素的累加和，就可以在 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和。因此我们接下来仅需完成两步即可： 第一步：搞出来前缀和矩阵 这里就要用到一维数组里面的拓展知识，我们要在矩阵的最上面和最左边添加上一行和一列0，这样我们就可以省去非常多的边界条件的处理（同学们可以自行尝试直接搞出来前缀和矩阵，边界条件的处理会让你崩溃的）。处理后的矩阵就像这样：

这样，我们填写前缀和矩阵数组的时候，下标直接从 1 开始，能大胆使用 i - 1 , j - 1 位置的值。 注意 dp 表与原数组 matrix 内的元素的映射关系：         i. 从 dp 表到 matrix 矩阵，横纵坐标减一；         ii. 从 matrix 矩阵到 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 - 1] 综上所述，我们的递推方程就是： 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] （为什么减一？因为要剔除掉 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]

2.3 代码实现 #include<vector> #include <iostream> using namespace std; int main() { int n = 0,m = 0,q = 0; cin >> n >> m >>q; //读入数据 vector<vector<int>> arr(n+1,vector<int>(m+1)); for(int i = 1;i <= n;i++) for(int j = 1;j<=m;j++) cin >> arr[i][j]; //处理前缀和矩阵 vector<vector<long>> dp(n+1,vector<long>(m+1)); for(int i = 1;i <= n;i++) { for(int j =1;j <= m;j++) { dp[i][j] = dp[i][j-1] + dp[i-1][j] + 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; } return 0; }

三、寻找数组的中心下标  3.1 题目

3.2 思路

从中心下标的定义可知，除中心下标的元素外，该元素左边的「前缀和」等于该元素右边的「后缀和」。 ▪ 因此，我们可以先预处理出来两个数组，一个表示前缀和，另一个表示后缀和。 ▪ 然后，我们可以用一个 for 循环枚举可能的中心下标，判断每一个位置的「前缀和」以及「后缀和」，如果二者相等，就返回当前下标。

3.3 代码实现 class Solution { public: int pivotIndex(vector<int>& nums) { // lsum[i] 表示：[0, i - 1] 区间所有元素的和 // rsum[i] 表示：[i + 1, n - 1] 区间所有元素的和 int n = nums.size(); vector<int> lsum(n), rsum(n); // 预处理前缀和后缀和数组 for (int i = 1; i < n; i++) lsum[i] = lsum[i - 1] + nums[i - 1]; for (int i = n - 2; i >= 0; i--) rsum[i] = rsum[i + 1] + nums[i + 1]; // 判断 for (int i = 0; i < n; i++) if (lsum[i] == rsum[i]) return i; return -1; } };

 

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

4.2 思路

注意题目的要求，不能使用除法，并且要在 O(N) 的时间复杂度内完成该题。那么我们就不能使用暴力的解法，以及求出整个数组的乘积，然后除以单个元素的方法。 继续分析，根据题意，对于每一个位置的最终结果 ret[i] ，它是由两部分组成的：         i. nums[0] * nums[1] * nums[2] * ... * nums[i - 1]         ii. nums[i + 1] * nums[i + 2] * ... * nums[n - 1] 于是，我们可以利用前缀和的思想，使用两个数组 post 和 suf，分别处理出来两个信息：         i. post 表示：i 位置之前的所有元素，即[0, i - 1] 区间内所有元素的前缀乘积，         ii. suf 表示： i 位置之后的所有元素，即[i + 1, n - 1] 区间内所有元素的后缀乘积 然后再处理最终结果。

4.3 代码实现 class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> f(n,1),g(n,1);//注意细节 //预处理 for(int i = 1;i < n;i++) f[i] = nums[i-1] * f[i-1]; for(int i = n-2; i >= 0; i--) g[i] = nums[i+1] * g[i+1]; vector<int> ret(n); for(int i = 0; i < n;i++) ret[i] = f[i] * g[i]; return ret; } };

五、和为 K 的子数组 5.1 题目

5.2 思路

设 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 。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。

5.3 思路 class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> hash; // 统计前缀和出现的次数 hash[0] = 1; int ret = 0,sum = 0; for(auto x : nums) { sum += x; // 计算当前位置的前缀和 if(hash.count(sum - k)) // 统计个数 ret += hash[sum-k]; hash[sum]++; } return ret; } };

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

6.2 思路

本题需要的前置知识： • 同余定理 如果 (a - b) % n == 0 ，那么我们可以得到一个结论： a % n == b % n 。用文字叙述就是，如果两个数相减的差能被 n 整除，那么这两个数对 n 取模的结果相同。 例如： (26 - 2) % 12 == 0 ，那么 26 % 12 == 2 % 12 == 2 。 • c++ 中负数取模的结果，以及如何修正「负数取模」的结果         a. c++ 中关于负数的取模运算，结果是「把负数当成正数，取模之后的结果加上一个负号」。例如： -1 % 3 = -(1 % 3) = -1         b. 因为有负数，为了防止发生「出现负数」的结果，以 (a % n + n) % n 的形式输出保证为 正。例如： -1 % 3 = (-1 % 3 + 3) % 3 = 2

思路与 和为 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 。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前 缀和出现的次数。

6.3 代码实现 class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int,int> hash; hash[0 % k] = 1; //0这个数的余数 hash[0]=1 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 题目

7.2 思路

暴力解法就是枚举所有的子数组，然后判断子数组是否满足要求

稍微转化一下题目，就会变成我们熟悉的题： • 本题让我们找出一段连续的区间， 0 和 1 出现的次数相同。 • 如果将 0 记为 -1 ， 1 记为 1 ，问题就变成了找出一段区间，这段区间的和等于 0 。 • 于是，就和 和为 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]的位置。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边记录第一次出现该前缀和的位置。

7.3 代码实现 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.1 题目

8.2 思路

如果没有看懂题目可以画个图理解一下

二维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对应区域的「左上角」以及「右下角」的坐标（推荐大家画图） 左上角坐标： 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) 。

8.3 代码实现 class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { int m = mat.size(),n = mat[0].size(); //1. 预处理一个前缀和矩阵 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][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1]; //2. 使用 vector<vector<int>> answer(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(m-1,i+k) + 1 ,y2 = min(n-1,j+k) + 1; answer[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]; } } return answer; } };

---

本篇完，下篇见！