【基础算法总结】前缀和

一，前缀和算法介绍

   前缀和也是基础算法之一，它一般应用于快速求出某个连续区间的和/积。前缀和一般包罗一维前缀和，二维前缀和，其实它的做题流程有一点点像动态规划的感觉。前缀和算法的时间复杂度是O(1)。
    前缀和与二分查找类似，也是有固定模板的，下面的前两题分别就是一维/二维的前缀和模板题。
  二，算法原理和代码实现

【模板】前缀和

算法原理：
   解法1：暴力解法，O(n*q)。就是根据它给的区间，一个一个数加起来，绝对超时。
    解法2：前缀和，O(q)+O(n)。
使用前缀和算法的固定流程：
(1) 预处理惩罚出来一个前缀和数组
创建一个dp数组，与原数组同规模巨细
dp中每个元素 dp 表示：arr数组中 [1,i ] 区间全部元素的和。
可得递推公式：dp = dp[i - 1] + arr

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

  细节题目：
   为什么下标要从1开始？
假如下标从0开始，会出现界限题目 ，根据上面的公式分析：

下标从1开始就是为了处理惩罚界限环境。
  代码实现：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. int main()
6. {
7.    // 读入数据
8.    int n, q;
9.    cin >> n >> q;
10.    vector<int> arr(n+1);
11.    for(int i = 1; i <=n; i++)
12.         cin >> arr[i];
14.     // 预处理前缀和数组
15.     vector<long long> dp(n+1); // 防溢出
16.     for(int i = 1; i <= n; i++)
17.         dp[i] = dp[i-1] + arr[i];
18.    
19.     // 使用前缀和数组
20.     while(q--)
21.     {
22.         int left, right;
23.         cin >> left >> right;
24.         cout << dp[right] - dp[left-1] << endl;
25.     }
26. }

复制代码

【模板】二维前缀和

算法原理：
   解法1：暴力解法，O(n * m * q)。就是根据给的两个坐标，一个一个数加，绝对超时。
  解法2：前缀和，O(m * n)+O(q)。
下面的内容将详细介绍前缀和矩阵的处理惩罚和使用：
(1) 预处理惩罚出一个前缀和矩阵
创建一个前缀和数组dp，巨细规模与arr相同。
dp[j] 表示：从[1][1] 位置到 [j] 位置，这段区间内里全部元素和。
以arr矩阵中的 [j] 位置为参考，可以把arr矩阵分成4块：
dp[j] = dp[i - 1][j] + dp[j - 1] + arr[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]

细节处理惩罚：
参考上一题
代码实现：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. int main()
6. {
7.    int n, m, q;
8.    cin >> n >> m >> q;
9.    // 输入数据
10.    vector<vector<long long>> arr(n+1, vector<long long>(m+1));
11.    for(int i = 1; i <= n; i++)
12.         for(int j = 1; j <= m; j++)
13.             cin >> arr[i][j];
15.     // 预处理前缀和矩阵
16.     vector<vector<long long>> dp(n+1, vector<long long>(m+1));
17.     for(int i = 1; i <= n; i++)
18.         for(int j = 1; j <= m; j++)
19.             dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];
21.     // 使用前缀和数组
22.     int x1, y1, x2, y2;
23.     while(q--)
24.     {
25.         cin >> x1 >> y1 >> x2 >> y2;
26.         cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] << endl;
27.     }
28. }

复制代码

724.探求数组的中心下标

算法原理：
   解法1：暴力求解，O(N^2)。遍历数组，每次固定一个下标，再分别盘算左右双方区间的和，进行比较，绝对超时。
    解法2：使用前缀和思想。
(1) 预处理惩罚
由于会涉及前后两个区间的求和，所以在预处理惩罚时界说一个f表示前缀和数组，g表示后缀和数组：

(2) 使用数组
然后只必要遍历一遍数组，每次固定一个下标，判定 f == g ，假如相等则返回 i，否则返回 -1。
  细节题目：
   (1) 根据 f 和 g 的递推公式，填 f[0] 时会越界，填 g[n-1] 时，也会越界，所以要先初始化 f[0] = g[n-1] = 0。
(2) 在填dp表时，前缀和数组f从前今后填，后缀和数组g从后往前填。
  代码实现：

1. class Solution
2. {
3. public:
4.     int pivotIndex(vector<int>& nums)
5.     {
6.         int n = nums.size();
7.         // 预处理前缀和，后缀和数组
8.         vector<int> f(n);
9.         vector<int> g(n);
10.         f[0] = 0, g[n-1] = 0; // 初始化
12.         for(int i = 1; i < n; i++)
13.             f[i] = f[i-1] + nums[i-1];
15.         for(int j = n-2; j >= 0; j--)
16.             g[j] = g[j+1] + nums[j+1];
17.         
18.         // 使用数组
19.         for(int k = 0; k < n; k++)
20.             if(f[k] == g[k])
21.                 return k;
22.         
23.         return -1;
24.     }
25. };

复制代码

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

算法原理：
   这道题和上一题根本上是一模一样的，也使用前缀和思想，只是本题是算乘法，上一题是算加法。
    (1) 预处理惩罚
由于会涉及前后两个区间的乘积，所以在预处理惩罚时界说一个f表示前缀积数组，g表示后缀积数组：

(2) 使用数组

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

1. class Solution
2. {
3. public:
4.     vector<int> productExceptSelf(vector<int>& nums)
5.     {
6.         // 预处理前缀积，后缀积数组
7.         int n = nums.size();
8.         vector<int> f(n), g(n);
9.         f[0] = g[n-1] = 1; // 初始化
11.         for(int i = 1; i < n; i++)
12.             f[i] = f[i-1] * nums[i-1];
13.         
14.         for(int j = n-2; j >= 0; j--)
15.             g[j] = g[j+1] * nums[j+1];
17.         // 使用数组
18.         vector<int> ret;
19.         for(int k = 0; k < n; k++)
20.             ret.push_back(f[k] * g[k]);
22.         return ret;
23.     }
24. };

复制代码

560.和为k的子数组

算法原理：
   我们在 [滑动窗口] 系列中做过一道和本题非常类似的，只不外那道题目中的数据都是正整数，一直累加，结果是单调递增的，所以才可以用 “滑动算法"思想(本质就是"同向双指针”)进行优化。但是这道题中有0和负数，相加的结果不是单调递增的，不能使用 “滑动窗口”。
    这道题可以使用：前缀和+哈希表。
我们引入"以 i 位置为结尾的全部的子数组"，如图，所以可以把题目中要求的"和为 k 的子数组"，转化成：在区间 [0, i-1] 中，有多少个前缀和等于 sum - k。
如何快速的统计前缀和个数呢？就要使用哈希表，把每次盘算的 sum - k 都扔进哈希表中，同时统计次数。
下图里绿色部分的表示前缀和：

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

1. class Solution
2. {
3. public:
4.     int subarraySum(vector<int>& nums, int k)
5.     {
6.         unordered_map<int, int> hash; // 统计前缀和出现的次数
7.         hash[0] = 1;
8.         
9.         int sum = 0, ret = 0;
10.         for(auto e : nums)
11.         {
12.             sum += e; // 计算当前位置的前缀和
13.             if(hash.count(sum - k)) ret += hash[sum - k]; // 统计个数
14.             hash[sum]++; // 把当前的前缀和扔进哈希表
15.         }
16.         return ret;
17.     }
18. };

复制代码

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

算法原理：
这道题和上一题太相似了，而且也不能用"滑动窗口"优化，缘故原由同上。
   在解决这题之前，先补充两个涉及的知识：
(1) 同余定理：若两数之差整除 p，则这两个数分别对 p 取模，余数相等。

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

    与上一题相同，本题还是使用：前缀和+哈希表
我们也引入"以 i 位置为结尾的全部的子数组"，如图，所以可把本题中要求的"和可被 k 整除的非空子数组的数量"转化为：在 [0, i-1] 区间中，找到有多少个前缀和的余数等于 (sum % k + k) % k 。
如何快速的统计前缀和个数呢？就要使用哈希表。把每次盘算的 (sum % k + k) % k 都扔进哈希表中，同时统计次数。
下图里绿色部分的表示前缀和：

  细节题目：
参考上一题
代码实现：

1. class Solution
2. {
3. public:
4.     int subarraysDivByK(vector<int>& nums, int k)
5.     {
6.         unordered_map<int, int> hash;
7.         hash[0 % k] = 1; // 0这个数的余数
9.         int sum = 0, ret = 0;
10.         for(auto x : nums)
11.         {
12.             sum += x;
13.             int r = (sum % k + k) % k; // 修正后的余数
14.             if(hash.count(r) ret += hash[r]; // 统计结果
15.             hash[r]++;
16.         }
17.         return ret;
18.     }
19. };

复制代码

525.连续数组

算法原理：
   这道题假如按题目要求直接找相同数量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。

  代码实现：

1. class Solution
2. {
3. public:
4.     int findMaxLength(vector<int>& nums)
5.     {
6.         unordered_map<int, int> hash;
7.         hash[0] = -1; // 默认有一个前缀和为 0 的情况
9.         int sum = 0, ret = 0;
10.         for(int i = 0; i < nums.size(); i++)
11.         {
12.             // 计算当前位置前缀和，把 -1 变 0
13.             sum += nums[i] == 0 ? -1 : 1;
15.             // 如果已经存在了，就不入哈希，更新长度，不存在就入哈希
16.             if(hash.count(sum)) ret = max(ret, i - hash[sum]);
17.             else hash[sum] = i;
18.         }
19.         return ret;
20.     }
21. };

复制代码

1314.矩阵区域和

算法原理：
   先明白题目意思：

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

代码实现：

1. class Solution
2. {
3. public:
4.     vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
5.     {
6.         int m = mat.size(), n = mat[0].size();
7.         vector<vector<int>> dp(m+1, vector<int>(n+1));
9.         // 预处理前缀和矩阵
10.         for(int i = 1; i <= m; i++)
11.             for(int j = 1; j <= n; j++)
12.                 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
14.         // 使用前缀和矩阵
15.         vector<vector<int>> ans(m, vector<int>(n));
16.         int x1 = 0, y1 = 0, x2 = 0 ,y2 = 0;
17.         for(int i = 0; i < m; i++)
18.         {
19.             for(int j = 0; j < n; j++)
20.             {
21.                 x1 = max(0, i-k) + 1, y1 = max(0, j-k) + 1;
22.                 x2 = min(i+k, m-1) + 1, y2 = min(j+k, n-1) + 1;
23.                 ans[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
24.             }
25.         }
26.         return ans;
27.     }
28. };

复制代码

三，算法总结

   通过上面若干道题目要掌握使用前缀和的两个步骤：一是预处理惩罚前缀和数组，这里要先明确 dp[j] 的含义，再推导递推公式，二是使用前缀和数组，其实就是在预处理惩罚好的 dp 数组中直接拿值，这一步的时间复杂度是O(1)。要留意的细节点就是使用原数组填 dp 数组的界限题目。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。