网站如何做二级栏目,wordpress分类id在哪里,免费域名查询网站,美工设计网页培训✨✨✨学习的道路很枯燥#xff0c;希望我们能并肩走下来! 文章目录 目录 文章目录 前言 一. 前缀和算法的介绍 二、前缀和例题 2.1 【模版】前缀和 2.2 【模板】二维前缀和 2.3 寻找数组的中间下标 2.4 除自身以外数组的乘积 2.5 和为k的子数组 2.6 和可被k整除的子数组 2.7 … ✨✨✨学习的道路很枯燥希望我们能并肩走下来! 文章目录 目录 文章目录 前言 一. 前缀和算法的介绍 二、前缀和例题 2.1 【模版】前缀和 2.2 【模板】二维前缀和 2.3 寻找数组的中间下标 2.4 除自身以外数组的乘积 2.5 和为k的子数组 2.6 和可被k整除的子数组 2.7 连续数组 2.8 矩阵区域和 总结 前言
本篇详细介绍了前缀和算法的使用让使用者了解前缀和而不是仅仅停留在表面 文章可能出现错误如有请在评论区指正让我们一起交流共同进步 一. 前缀和算法的介绍
前缀和算法是一种用空间换时间的算法他常常用于解决某些题目或者作为某些高级算法的组成部分。
例如让你求某个矩阵一维的子矩阵的最大值如果使用暴力解法它的时间复杂度将会是O(n^2) 但如果使用该算法就可以使其时间复杂度降低一个维度也就是O(N).
前缀和 是从 nums 数组中的第 0 位置开始累加到第 位置的累加结果我们常把这个结果保存到数组 Sum 中记为 Sum[i]。
前缀和算法的本质是一个简单动态规划 接下来我们使用一些例题来介绍一下
二、前缀和例题
2.1 【模版】前缀和
牛客网—【模版】前缀和 #include iostream
#includevector
using namespace std;int main() {//1.读入数据int n ,q;cinnq;vectorint arr(n1);for(int i 1;in;i) cinarr[i];//2. 预处理出来个前缀和数组vectorlong long dp(n1); //防止溢出for(int i 1;in;i) dp[i] dp[i-1]arr[i];//3.使用前缀和数组int l 0, r 0;while(q--){cinlr;coutdp[r]-dp[l-1]endl;}return 0;}
2.2 【模板】二维前缀和
牛客网—【模版】二维前缀和 #include iostream
#include vector
using namespace std;int main() {int n,m,q;cinnmq;vectorvectorint arr(n1,vectorint(m1));for(int i 1;in;i){for(int j 1;jm;j){cinarr[i][j];}}vectorvectorlong long dp(n1,vectorlong long(m1));for(int i 1;in;i){for(int j 1;jm;j){dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] - dp[i-1][j-1];}}int x1 0,y1 0,x2 0 ,y2 0;while(q--){cinx1y1x2y2;coutdp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]endl;}return 0;
} 2.3 寻找数组的中间下标
724. 寻找数组的中心下标 - 力扣LeetCode class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint f(n), g(n);//1. 预处理前缀和数组和后缀和数组for(int i 1;in;i)f[i] f[i-1] nums[i-1];for(int i n-2;i0;i--)g[i] g[i1] nums[i1];//2. 使用for(int i 0;in;i)if(f[i] g[i]) return i;return -1;}
}; 2.4 除自身以外数组的乘积
238. 除自身以外数组的乘积 - 力扣LeetCode class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();//细节处理vectorint f(n,1), g(n,1);//前缀和和后缀和for(int i 1;in;i)f[i] f[i-1]*nums[i-1];for(int i n-2;i0;i--)g[i] g[i1]*nums[i1];//使用vectorint ret(n);for(int i 0;in;i)ret[i] f[i] * g[i];return ret;}
}; 2.5 和为k的子数组
560. 和为 K 的子数组 - 力扣LeetCode class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,int hash; //统计前缀和出现的次数hash[0] 1;int sum 0, ret 0;for(autox : nums){sumx; //计算当前位置的前缀和if(hash.count(sum-k)) rethash[sum-k]; //统计个数hash[sum];}return ret;}
};
2.6 和可被k整除的子数组
974. 和可被 K 整除的子数组 - 力扣LeetCode class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,int hash;hash[0 % k] 1; //0 这个数的余数int sum 0, ret 0;for(auto x : nums){sumx; //算出当前位置的前缀和if(hash.count((sum%kk)%k)) rethash[(sum%kk)%k]; //修正后的余数统计结果hash[(sum%kk)%k];}return ret;}
}; 2.7 连续数组
525. 连续数组 - 力扣LeetCode class Solution {
public:int findMaxLength(vectorint nums) {unordered_mapint,int hash;hash[0] -1; //默认有一个前缀和为0的情况int sum 0, ret 0;for(int i 0;inums.size();i){sumnums[i] 0 ? -1 : 1; //计算当前位置的前缀和if(hash.count(sum)) ret max(ret,i - hash[sum]);else hash[sum] i;}return ret;}
}; 2.8 矩阵区域和
1314. 矩阵区域和 - 力扣LeetCode class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();vectorvectorint dp(m1,vectorint(n1));for(int i 1;im;i)for(int j 1;jn;j)dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i-1][j-1];vectorvectorint answer(m,vectorint(n));for(int i 0;im;i)for(int j 0;jn;j){int x1 max(0,i-k)1;int y1 max(0,j-k)1;int x2 min(m-1,ik)1;int y2 min(n-1,jk)1;answer[i][j] dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1];}return answer;}
}; 总结
✨✨✨各位读友本篇分享到内容是否更好的让你理解前缀和算法如果对你有帮助给个赞鼓励一下吧 世上没有绝望的处境只有对处境绝望的人。 感谢每一位一起走到这的伙伴我们可以一起交流进步一起加油吧
