本文主要是介绍【LeetCode热题100】前缀和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这篇博客共记录了8道前缀和算法相关的题目，分别是：【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。
#include <iostream>
#include <vector>
using namespace std;int main()
{//1. 读取数据int n = 0, q = 0;cin >> n >> q;vector<int> nums(n+1);vector<long long> dp(n+1);for(int i = 1; i<= n ;i++){cin >> nums[i];//2. 预处理出来一个前缀和数组dp[i] = dp[i-1] + nums[i];}//3.使用前缀和数组int l = 0,r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] << endl;}return 0;
}题目分析：首先来看暴力解法，题目让我们求l到r的和，我们可以找到l，然后依次往后累加，直到加到r，然后执行q次，所以这种暴力解法的时间复杂度是O(N*q)。这种暴力解法肯定过不了。所以，我们要使用前缀和方法解决这个问题。所谓前缀和，就是快速求出数组中某一个连续区间的和。快速：使用O(1)的时间复杂度找到一次结果。我们从题目中看到，数组元素下标是从1开始的，下标为0的位置我们默认为0。具体来说，第一步：预处理出来一个前缀和数组dp，其中dp[i]表示[1，i]区间内所有元素的和，dp[0]默认设为0，dp[i]=dp[i-1]+arr[i]。第二步：使用前缀和数组。当我们想求[l, r]区间的和时，可以直接用dp[r]-dp[l-1]求解。这样直接求解的时间复杂度为O(1)。
细节问题：为什么我们的下标要从1开始计数？为了处理边界情况。如果下标从0开始，比如，要求下标0-2之间元素之和，按照上面的方法就是求dp[2]-dp[-1]，明显越界了，对于这种情况，还需要单独处理。
#include <iostream>
#include <vector>
using namespace std;int main()
{//1.读入数据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];}}//2.预处理出一个前缀和矩阵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][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1];}}//3.利用前缀和矩阵int x1 = 0, x2 = 0, y1 = 0, y2 = 0;while(q--){cin >> x1 >> y1 >> x2 >> y2 ;cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;}
}题目分析：最开始我们想到的肯定是暴力求解，但是很明显暴力求解的时间复杂度很高，是O(n*m*q)，所以我们再来说一种更好的解法--前缀和，第一步，我们预处理出来一个前缀和矩阵dp，dp[i][j]表示从[1][1]位置到[i][j]位置这段区间里面所有元素的和。第二步，使用前缀和矩阵。具体计算过程如下：
class Solution {
public:int pivotIndex(vector<int>& nums) {//1.先创建前缀和数组f，后缀和数组gint n = nums.size();vector<int> f(n);vector<int> g(n);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];}//2.使用前缀和数组和后缀和数组for(int i = 0 ; i < n ; i++){if(f[i] == g[i]) return i;}return -1;}
};
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n);vector<int> g(n);vector<int> ret(n);f[0] = 1,g[n-1] = 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];}//2.使用前缀和数组for(int i = 0; i < n ; i++){ret[i] = f[i] * g[i];}return ret;}
};
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash; // 统计前缀和出现的次数int sum = 0, ret = 0;hash[0] = 1;for(auto c : nums){sum += c; //计算当前位置的前缀和if(hash.count(sum - k)) ret += hash[sum - k]; //统计个数hash[sum]++;}return ret;}
};题目分析：对于这道题，如果使用暴力求解，其时间复杂度是O(N2)，所以我们换一种方法，我们使用前缀和的思想，在以i为结尾的所有子数组中找，假设以i为结尾的子数组前缀和是sum[i]，那么就是在[0,i-1]区间中，有多少个前缀和为sum[i]-k。在找有多少个前缀和为sum[i]-k时，我们可以将之前的前缀和放到一个哈希表中，哈希表的key是前缀和，value前缀和的次数。其实我们不需要搞出一个前缀和数组sum[i]，而只需有一个变量sum就行，sum是前i个元素的和。
有几个细节需要处理：1.前缀和加入哈希表的时机：在计算i位置之前，哈希表里只保存[0,i-1]位置的前缀和。2.不用真的创建一个前缀和数组，用一个变量sum来标记前一个位置的前缀和即可。3.如果整个前缀和等于k呢，其实我们应该在开始时设置hash[0]=1。
class Solution
{
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash;int sum = 0;int reminder = 0;int ret = 0;hash[0] = 1; // 0这个数的余数for(auto e : nums){sum += e; // 当前位置的前缀和reminder = (sum % k + k)%k; //修正后的余数if(hash.count(reminder)) ret += hash[reminder]; //统计结果hash[reminder]++;}return ret;}
};题目分析：对于这道题，我们先要补充两个知识：1.同余定理，(a-b)/p = k，可以得出a%p=b%p。2.C++/JAVA中，负%正 = 负，修正-->(a%p+p)%p，这样得到的结果就是一个正确的正数。好了，有了这两个补充知识，剩下的就和上道题几乎一样了。
class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;int sum = 0;hash[0] = -1; //默认有一个前缀和为0的情况int 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;}
};题目分析：这道题如果直接求会比较困难，我们可以转化一下，将所有的0改为-1，问题就转化为在数组中，找出最长的子数组，使子数组中所有元素的和为0。这样就和之前和为k的子数组的做法很像，也是使用前缀和+哈希表。但是还是有一些区别，1.哈希表中存什么呢？hash<int,int>的第一个int应该是前缀和，第二个int应该是下标。2.什么时候存入哈希表？使用完之后，丢进哈希表。3.如果有重复的<sum,i>，如何存？只保留前面的那一对<sum,i>。4.默认的前缀和为0的情况，如何存？hash[0]=-1。5.长度怎么算？i-j。
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-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];}}//2.使用vector<vector<int>> ret(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,x2 = min(m-1 , i+k)+1,y2 = min(n-1,j+k)+1;ret[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];}}return ret;}
};题目分析：这道题很明显需要用到二维数组前缀和，首先，我们要预处理得到一个前缀和数组dp，dp元素的求法如下图（先以mat的起始下标为(1,1)为例）：
得到前缀和数组之后，假设我们要求(x1,y1)~(x2,y2)区间元素的和，其算法如下图：
按照题目要得到的矩阵，anwser[i][j]所求的就是[i-k][j-k]~[i+k][j+k]区间元素的和，就可以使用上面求ret的方法，但是i-k、j-k、i+k、j+k有可能越界，所以我们不得不考虑这些越界情况：
但是，这道题的mat的其实下标是从0开始的，我们就必须考虑下标的映射关系，dp数组必须要多加一行多加一列，然后dp就可以从[1,1]下标开始，所以，在求dp矩阵时，在找原始矩阵mat时下标要－1。然后在使用dp表求ans矩阵时，要对下标＋1，这其实可以在我们计算(x1,y1)~(x2,y2)时，就给下标+1。
这篇关于【LeetCode热题100】前缀和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
