算法练习：前缀和

1. 一维前缀和

1. 题目信息：
   
2. 题目链接：
   一维前缀和
3. 思路：求前缀和数组，sum = dp[r] - dp[l - 1]

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n = 0;int q = 0;cin >> n >> q;//先求前缀和数组int num = 0;//计算时可能溢出vector<long long> dp;dp.push_back(0);for(int i = 0; i < n; i++){cin >> num;dp.push_back(num + dp[i]);}//求询问区间之和//dp[i] - dp[i - 1]//计算时可能溢出vector<long long> ret;int left = 0,right = 0;for(int i = 0; i < q; i++){cin >> left >> right;ret.push_back(dp[right] - dp[left - 1]);}for(auto e : ret){cout << e << endl;}return 0;    
}

优化：

int main() 
{int n = 0;int q = 0;cin >> n >> q;//先求前缀和数组int num = 0;//默认初始化为0vector<int> arr(n + 1);for(int i = 1; i < n + 1; i++){cin >> num;arr[i] = num;}//防溢出vector<long long> dp(n + 1);for(int i = 1; i < n + 1; 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. 题目链接：
   二维前缀和
3. 思路：二维前缀和

int main()
{int n = 0, m = 0, q = 0;//先遍历，得值    cin >> n >> m >> q;vector<vector<long long>> arr;vector<long long> part(m + 1);for (int i = 0; i < n + 1; i++){arr.push_back(part);}vector<vector<long long>> dp(arr);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> arr[i][j];}}//求前缀和数组for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];}}//求区间值//x1,y1小，x2,y2大int x1, x2, y1, y2 = 0;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. 题目信息：
   
2. 题目链接：
   寻找数组的中心下标
3. 思路：正向与逆向前缀和数组，边界处理，特殊情况处理

class Solution
{
public:int pivotIndex(vector<int>& nums){int n = nums.size();vector<int> dp1(n);vector<int> dp2(n);//空if(nums.size() == 1){return 0;}int left = 0, right = nums.size() - 1;//求前缀和数组//顺序while (left < nums.size()){if (left > 0){dp1[left] = nums[left] + dp1[left - 1];}else{dp1[left] = nums[left];}left++;}//倒序while (right >= 0){if (right < nums.size() - 1){dp2[right] = nums[right] + dp2[right + 1];}else{dp2[right] = nums[right];}right--;}//遍历求中间结点for (int cur = 0; cur < nums.size(); cur++){//dp1顺序//dp2倒序if (cur == 0){if (dp2[cur + 1] == 0){return cur;}}else if (cur == nums.size() - 1){if (dp1[cur - 1] == 0){return cur;}}else{if (dp1[cur - 1] == dp2[cur + 1]){return cur;}}}return -1;}
};

优化：

class Solution 
{
public:int pivotIndex(vector<int>& nums) {int n = nums.size();//顺序vector<int> f(n);//逆序vector<int> g(n);//边界问题特殊处理f[0] = 0;//f[i] -> [0, i - 1]for(int i = 1; i < n; i++){f[i] = nums[i - 1] + f[i - 1];}g[n - 1] = 0;for(int i = n - 2; i >= 0; i--){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. 除自身以外数组的乘积

1. 题目信息：
   
2. 题目链接：
   除自身以外数组的乘积
3. 思路：前缀 + 后缀数组

class Solution 
{
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n);vector<int> g(n);f[0] = nums[0];for(int i = 1; i < n; i++){f[i] = nums[i] * f[i - 1];}g[n - 1] = nums[n - 1];for(int i = n - 2; i >= 0; i--){g[i] = nums[i] * g[i + 1];}vector<int> ret(n);for(int i = 0; i < n; i++){if(i == 0){ret[i] = g[i + 1];}else if(i == n - 1){ret[i] = f[i - 1];}else{ret[i] = g[i + 1] * f[i - 1];}}return ret;}
};

优化：

class Solution 
{
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n);vector<int> g(n);f[0] = 1;//顺序for(int i = 1; i < n; i++){f[i] = f[i - 1] * nums[i - 1];}g[n - 1] = 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的子数字

1. 题目信息：
   
2. 题目链接：
   和为k的子数组
3. 思路：前缀和，元素没有单调性，无法使用滑动窗口，逆向求sum - k，可以求得为i为尾的所有数组

class Solution 
{
public:int subarraySum(vector<int>& nums, int k) {int ret = 0;unordered_map<int ,int> hash;//sum - k == 0时，即sum就为khash[0] = 1;int sum = 0;//用哈希表代替遍历for(auto e : nums){sum += e;if(hash.count(sum - k)){ret += hash[sum - k];}//插入哈希表//可能存在重复前缀和hash[sum]++;}return ret;}
};

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

1. 题目信息：
   
2. 题目链接：
   和可被k整除的子数组
3. 思路：前缀和，哈希表，同余定理，C++中负数除以整数的余数修正(num % k + k) % k

class Solution 
{
public:int subarraysDivByK(vector<int>& nums, int k) {int sum = 0;unordered_map<int,int> hash;int ret = 0;int count = 0;//sum % k 本身就符合要求hash[0] = 1;for(auto e : nums){sum += e;//(sum1 - sum2) % k == 0//同余定理//负数除整数的余数//哈希表中存余数if(hash.count((sum % k + k) % k)){ret += hash[(sum % k + k) % k];}hash[(sum % k + k) % k]++;}return ret;}
};

7. !连续数组

1. 题目信息：
   
2. 题目链接：
   连续数组
   3.思路：前缀加哈希表，求长度，记录下标

class Solution 
{
public:int findMaxLength(vector<int>& nums) {for(auto& e : nums){if(e == 0){e = -1;}}unordered_map<int,int> hash;int sum = 0;int len = 0;//细节，刚好sum为0hash[0] = -1;for(int i = 0; i < nums.size(); i++){//将所有的前缀和与对应下标记录至哈希表中sum += nums[i];//返回的是长度，最长数组的长度if(hash.count(sum) && len < i - hash[sum]){len = i - hash[sum];}//不存在添加下标if(!hash.count(sum)){hash[sum] = i;}}return len;}
};

@8. 矩阵区域和

1. 题目信息：
   
2. 题目链接：
   矩阵区域和
3. 思路：前缀和二维数组，边界问题分析

思路：

边界问题：

class Solution 
{
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k){vector<int> part1(mat[0].size(), 0);vector<vector<int>> answer(mat.size(), part1);vector<int> part2(mat[0].size() + 1, 0);vector<vector<int>> dp(mat.size() + 1, part2);//二维数组的前缀和for (int i = 1; i < dp.size(); i++){for (int j = 1; j < dp[0].size(); j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];}}for (int i = 0; i < mat.size(); i++){for (int j = 0; j < mat[0].size(); j++){int sum = 0;//右下角//边界情况，修正int pos1 = i + k + 1;int pos2 = j + k + 1;if (pos1 >= dp.size()){pos1 = dp.size() - 1;}if (pos2 >= dp[0].size()){pos2 = dp[0].size() - 1;}sum += dp[pos1][pos2];//右上角pos1 = i - k;pos2 = j + k + 1;//i符合，j不符合if (pos1 >= 1 && pos2 >= dp[0].size()){pos2 = dp[0].size() - 1;}if (pos1 >= 1 && pos2 < dp[0].size()){sum -= dp[pos1][pos2];}//左下角pos1 = i + k + 1;pos2 = j - k;//i不符合，j符合if (pos1 >= dp.size() && pos2 >= 1){pos1 = dp.size() - 1;}if (pos1 < dp.size() && pos2 >= 1){sum -= dp[pos1][pos2];}//左上角if (i - k >= 1 && j - k >= 1){sum += dp[i - k][j - k];}answer[i][j] = sum;}}return answer;}
};