前缀和（算法4）

1.一维前缀和模板一维前缀和快速求出数组某一连续区间的和一维前缀和模板第一步先预处理出一个数组dp[i] dp[i-1]arr[i]//递推初始化dpdp[i]表示下标为[1, i]的所有数的和第二步[r, l]区间和为dp[r]-dp[l-1]tips:下标从1开始方便处理边界情况添加辅助结点dp使用longlong防溢出模板题codelink:【模板】前缀和_牛客题霸_牛客网2.二维前缀和模板思路同上一维前缀和二维前缀和求所有dp[x][y]的和其中x∈[x1, x2],y∈[y1, y2]二维前缀和模板第一步初始化dp数组dp[i][j]表示所有x∈[1,i], y属于[1,j]和dp[x][y]和dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] arr[i][j]第二步使用dp解答问题[x1, y1] - [x2, y2] : dp[x2, y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]tips:dp最好long long防溢出模板题3.寻找数组的中心下标link. - 力扣LeetCode解法一前缀和思路直接套用一维前缀和模板具体见code注释codeclass Solution { public: int pivotIndex(vectorint nums) { //下标从1开始 //求第一个ans使得sum[ans-1] sum[nums.size()] - sum[ans] //return ans-1 nums.insert(nums.begin(), 0); int n nums.size(); vectorint dp(n, 0); //init dp for(int i 1; i n-1; i) { dp[i] dp[i-1] nums[i]; } // use dp for(int ans 1; ans n-1; ans) { if(dp[ans-1] dp[n-1]-dp[ans]) return ans-1; } return -1; } // bool check(int ans){} };解法二前缀和后缀和其实两个方法差不多 都可以4.除自身以外数组的乘机link238. 除自身以外数组的乘积 - 力扣LeetCode思路前缀乘积后缀乘积详见code注释codeclass Solution { public: vectorint productExceptSelf(vectorint nums) { //f[i], t[i]:[0,i], [i,nums.size()-1]前/后缀乘积 //answer f[i-1] * t[i1] int sz nums.size(); vectorint f(sz), t(sz), answer(sz); //init f() t() f[0] nums[0]; for(int i 1; i sz; i) { f[i] f[i-1]*nums[i]; } t[sz-1] nums[sz-1]; for(int i sz-2; i 0; i--) { t[i] t[i1]*nums[i]; } // f() t() - answer[] answer[0] t[1]; answer[sz-1] f[sz-2]; for(int i 1; i sz-1; i) { answer[i] f[i-1]*t[i1]; } return answer; } };5.和为k的子数组link:LCR 010. 和为 K 的子数组 - 力扣LeetCode思路前缀和hash具体见codecode注释codeclass Solution { public: int subarraySum(vectorint nums, int k) { //前缀和 //dp[i]表示nums[0, i]和 //遍历nums对nums[i]求[0, i-1]中的x使dp[x]k-dp[i] vectorint dp(nums.size()); int ans 0; //init dp dp[0] nums[0]; for(int i 1; i nums.size(); i) { dp[i] dp[i-1] nums[i]; } dp.insert(dp.begin(), 0); //dp hash unordered_mapint, int mymap {};//val-cnt for(int i 0; i dp.size(); i) { int target dp[i] - k; ansmymap[target]; mymap[dp[i]]; } return ans; } };优化后代码class Solution { public: int subarraySum(vectorint nums, int k) { //比上一次的优化 // 用int 变量sum取代dp // 初始mymap[0] 1代替dp.insert(dp.begin(), 0) int sum 0, ans 0; unordered_mapint, int mymap {{0, 1}}; for(auto e:nums) { sume; ansmymap[sum-k];//不可用map.count(),因为在非multi中map.count()必定返回1求key对应val应该用mymap.operator[] mymap[sum]; } return ans; } };6.和可被K整除的子数组link:974. 和可被 K 整除的子数组 - 力扣LeetCode思路前缀和hash表tips1.同余定理2.负数%正数C与java中负数%整数负数codeclass Solution { public: int subarraysDivByK(vectorint nums, int k) { //前缀和hash//nums[i] 可能小于等于0不可滑动窗口 //同余定理 //注意C中 负数%正数 负数 // vectorint dpmod(nums.size()); long long dpmod 0, ans 0; unordered_mapint, int mymap; //init dpmod mymap use mymap[0] 1; for(int i 0; i nums.size(); i) { dpmodnums[i]; dpmod (dpmod%k k)%k; ans mymap[dpmod]; mymap[dpmod]; } return ans; } };7.连续数组link525. 连续数组 - 力扣LeetCode思路前缀和 hash具体见codecode注释tip:通过判断cnt0-cnt1是否相等 来判断两点间01数量是否满足关系或0--1, 求和为0的最长连续子数组的最长长度解法一codeclass Solution { public: int findMaxLength(vectorint nums) { //没有单调性不能滑动窗口 //dp0[r]-dp0[l],dp1[r]-dp1[l] dp0[l]-dp1[l]dp0[r]-dp1[r] //使用前缀和求max(r-l) unordered_mapint, int sub_idx;//sub dp0[idx]-dp1[idx];{sub, sub_idx.count(sub)?sub:idx} int dp0 0, dp1 0; int ans 0; // 前缀和 sub_idx[0] -1; for(int i 0; i nums.size(); i) { nums[i]1 ? dp1 : dp0; int sub dp0 - dp1;//sub代表了[0, i]区间内0, 1个数关系 if(sub_idx.count(sub)) {//[0, i], [0, idx]的sub相同则说明区间[i1, idx]满足cnt0 cnt1 int idx sub_idx[sub]; ans max(ans, i - idx); } else { sub_idx[sub] i; } } return ans; } };解法二0--1, 求和为0的最长连续子数组长度8.矩阵区域和link1314. 矩阵区域和 - 力扣LeetCode思路二维前缀和模板codeclass Solution { public: vectorvectorint matrixBlockSum(vectorvectorint mat, int k) { //前缀和 vectorvectorint dp(mat.size(), vector(mat[0].size(), 0)); vectorvectorint ans(mat.size(), vector(mat[0].size(), 0)); //init dp for(int i 0; i mat.size(); i) { for(int j 0; j mat[0].size();j) { dp[i][j] (i-10 ? dp[i-1][j] : 0) (j-10?dp[i][j-1]:0) - ((i-10j-10)?dp[i-1][j-1]:0) mat[i][j]; } } //前缀和 for(int i 0; i ans.size(); i) { for(int j 0; j ans[0].size(); j) { int x1 max(i-k, 0), y1 max(j-k, 0); int x2 min(ik, int(ans.size()-1)), y2 min(jk, int(ans[0].size()-1)); ans[i][j] dp[x2][y2] - (x1-10?dp[x1-1][y2]:0) -(y1-1 0 ?dp[x2][y1-1]:0) (x1-10 y1-10 ? dp[x1-1][y1-1]:0); } } return ans; } };