【优选算法必修篇——前缀和】前缀和：『560. 和为 K 的子数组 1314.矩阵区域和』

个人主页MSTcheng · CSDN代码仓库MSTcheng · Gitee 精选专栏: 《C语言》《数据结构》《算法学习》《C由浅入深》座右铭路虽远行则将至事虽难做则必成前言上一篇文章中我们向大家介绍了二分算法本篇我们就来介绍一下前缀和算法。我们通过一道例题来讲解前缀和一、【模板】前缀和1.1题目解析1.2算法原理1、暴力算法上面有一个数组如果我们要计算某一个区间的值我们直接去暴力遍历那么我可以计算时间复杂度为O(N)的然后这只是一次计算题目中还要进行m次查询给出多个区间所以时间复杂度是O(n*m)。下面来看看基于暴力算法的优化2、使用前缀和细节问题为什么要从1开始计数为了处理边界情况如果我们从0开始那么要计算(0,2)区间的数不就是,dp[2]-dp[-1]了而-1是我们未定义的访问必然崩溃所以dp数组下标从1开始就是为了避免这样的情况发生。所以我们在设计dp数组的时候可以给dp[0]初始化一下将dp[0]设为0当然不同题目的要求不同不是所有情况都将dp[0]设为03、代码编写#includeiostream#includevectorusingnamespacestd;intmain(){//输入数据intn0,m0;cinnm;vectorintarr(n1);for(inti1;in;i){cinarr[i];}//预处理出来一个前缀和数组vectorlonglongdp(n1);//使用long long防止溢出for(inti1;in;i){dp[i]dp[i-1]arr[i];}//使用前缀和数组while(m--){intl0,r0;cinlr;coutdp[r]-dp[l-1]endl;}}二、【模板】二维前缀和2.1题目解析2.2算法原理注意1、在二维dp数组我们在与原数组arr同等大小的规模上在最上面和最坐标添加上一行和一列目的就是为了防止像一维dp数组那样出现未定义的情况比如dp[-1][-1]。2、同时我们要注意原arr数组与dp数组下面的映射关系从dp表到arr矩阵横纵坐标减⼀从arr矩阵到dp表横纵坐标加⼀。2.3代码编写#includeiostream#includevectorusingnamespacestd;intmain(){//输入数据intn0,m0,q0;cinnmq;//1、注意二维数组的初始化方式 题目要求arr数组行和列都从下标1开始//2、使用long long 防止溢出vectorvectorlonglongarr(n1,vectorlonglong(m1,0));for(inti1;in;i){for(intj1;jm;j){cinarr[i][j];}}//预处理出来一个前缀和数组 所以前缀和数组可以和arr数组一样大vectorvectorlonglongdp(n1,vectorlonglong(m1,0));for(inti1;in;i){for(intj1;jm;j){dp[i][j]dp[i-1][j]dp[i][j-1]arr[i][j]-dp[i-1][j-1];}}//使用前缀和数组 q次访问while(q--){intx10,y10,x20,y20;cinx1y1x2y2;longlongretdp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]dp[x1-1][y1-1];coutretendl;}}注意但是本题的arr数组下标题目要求是从1开始的所以与dp数组下标直接对应我们求dp[i][j]就是求arr[1][1]到arr[i][j]所有元素的值而不是求arr[0][0]到arr[i-1][j-1]的值所以本题的dp数组可以跟原数组一样大三、560. 和为 K 的子数组3.1题目解析3.2算法原理3.3代码编写classSolution{public:intsubarraySum(vectorintnums,intk){unordered_mapint,inthash;//默认第一个前缀和为1 当给出的数组已经等于k时就是一种情况 所以哈希表0的位置默认给成1hash[0]1;intsum0,ret0;//sum计算前缀和 ret统计最终结果for(autox:nums){sumx;//sum加等x后就变成了下一次的前缀和if(hash.count(sum-k)){//此时判断一下 哈希表里有没有满足sum-k 的前缀和存在 有的话ret就加等于满足sum-k 所有前缀和的次数rethash[sum-k];}hash[sum];//不断将前缀和放入哈希表}returnret;}};4、1314. 矩阵区域和4.1题目解析4.2算法原理4.3编写代码classSolution{public:vectorvectorintmatrixBlockSum(vectorvectorintmat,intk){//搞出一个dp数组intmmat.size();//m是行大小intnmat[0].size();//n是列大小//二维数组就相当于拿n个一维vector来初始化//注意dp数组要多一行多一列 因为dp数组默认从1开始//而dp[1]存的是mat[0]周围k个元素的和vectorvectorintdp(m1,vectorint(n1,0));for(inti1;im;i){for(intj1;jn;j){//这里要尤为注意mat[i-1][j-1]dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1];}}//使用dp数组//创建一个ans数组//int x10,y10,x20,y20;vectorvectorintans(m,vectorint(n));for(inti0;im;i){for(intj0;jn;j){//这里的x1x2y1y2都加一是因为加一才能与//dp数组的下标对应intx1max(0,i-k)1;inty1max(0,j-k)1;intx2min(m-1,ik)1;inty2min(n-1,jk)1;ans[i][j]dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1];}}returnans;}};五、总结一、最典型适用场景必用前缀和1、多次查询区间和给一个数组问很多次[l, r] 的和是多少→ 前缀和 O (1) 回答不用每次遍历。2、求有多少个子数组和 k最经典nums 中有多少个子数组和为 target→ 前缀和 哈希表 O (n)。3、求子数组和 ≥ k / ≤ k 的最短 / 最长长度正数组时前缀和 双指针 / 二分。4、环形数组、连续子数组和问题、拆成两段和用前缀和快速算。5、二维矩阵里求子矩阵和求矩形区域和 → 二维前缀和。6、需要快速比较多个区间的和比如判断哪段和最大 / 最小、是否相等。看到区间和、子数组和、多次查询和 → 前缀和会改数组 → 不用前缀和