前缀和模板全解析：从入门到精通

前缀和是一个有模版可以套的题目所以前两个题的模版比较重要1.一维前缀和【模版】题目来源【模板】前缀和_牛客题霸_牛客网这道题算是一个模版接下来前缀和题目要用到的一个模版先来看题目题目的意思很简单求出数组下标从l到r的元素之和要注意到的是数组的下标是从1开始的所以我们数组的空间要开n1的大小暴力解法很简单定义一个变量然后根据给出的查询次数遍历数组统计元素和就够了暴力解法的时间复杂度为o(n^2),每次遍历数组为on要遍历n次因为题目要求的是某一个区间的元素之和那我们是不是可以先将前n个数的和算出来然后放到一个数组里等需要的时候拿出来使用就好了根据上面讲的我们可以来设一个dp数组数组的元素是题目所给的数组前n个元素之和如图所示dp数组中第i个元素的值为原数组中前i个元素的和假设l2,r4,那么我们要输出的元素是不是就相当于dp[r]-dp[l-1]代码如下2.二维前缀和【模版】题目来源【模板】二维前缀和_牛客题霸_牛客网这道题跟一维前缀和同样可以看作一道模版题题目的意思就是让你求出数组中x1y1到x2y2这两个坐标间所有元素的和我们来画图分析我们需要先处理出来一个前缀和数组由于元素的下标是从1开始的所以我们要开n1行m1列并且将第一行和第一列的元素都处理成0代码如下3.寻找数组的中心下标题目来源724. 寻找数组的中心下标 - 力扣LeetCode这道题用前缀和来进行解答需要数组一个是前缀和一个是后缀和分别用来记录前面元素的和以及后面元素的和从前到后来对比每一个位置的前缀和和后缀和如果两个相当那么此时的下标i就是我们要求的中心下标因为0左边和size-1右边都相当于没有元素所以我们需要将0的前缀和置为0size-1的后缀和置为0代码如下4.除了自身以外数组的乘积题目来源238. 除了自身以外数组的乘积 - 力扣LeetCode这道题和上一道题很像上一道题要的是某个位置左右两边的和这一道题要求的是某个位置左右两边的积整体思路大差不差在边界处理由于是乘法上要求赋值为1而不是0具体代码如下5.和为k的总数组题目来源560. 和为 K 的子数组 - 力扣LeetCode老规矩先来想一个暴力的解法可以将每一个子数组列出来再计算其中的和但这样写时间复杂度肯定是超时的了当用暴力枚举一个个列出来时时间复杂度是o(n^2)并且这道题还不能够用双指针滑动窗口来进行优化因为数组中的元素不只是正数还可能会有负数或者零假如用双指针来进行优化就有可能出现下面这种情况因为right并不会往回走会导致漏掉其中的一些情况所以不能用双指针来进行优化我们可以画图来分析一下要找到有多少个和为k的子数组其实就相当于要找到多少个值为sum-k的前缀和元素那为什么不直接求有多少个值为k的前缀和元素呢如果这样做那么时间复杂度甚至比暴力解法还差对前缀和数组进行n次遍历并且每n次遍历都需要更换起点这样就是on^2的时间复杂度了然后之前还需要额外创建一个前缀和数组相当于o(n^2)o(n)并且假如直接求值为k的前缀和元素个数那么得到的结果只是从0到i-1里值为k的子数组个数是以0作为起点的可能会漏掉以其他位置为起点的情况但是假如求的是sum-k因为sum是会不断进行更新的所以并不会出现上面的情况所以问题就转换成了求值为sum-k的前缀和元素的个数把上面的转换搞懂后还有三个需要注意的细节问题1.假如数组所有元素之和为k那么我们这种方式要找的就是值为0的前缀和元素相当于在[0,-1]里去找值为0的个数但那个区间明显是不存在的因此在开始遍历数组之前我们需要来做一些特殊处理将hash[0]1;2.我们并不需要真的做一个前缀和数组我们要的只是sum-k中的sum因此可以用一个变量来进行替代3.在进行前缀和数组的检查之前我们要放到数组当中的值只是[0,i-1]这个区间的i以及i之后的并不需要考虑具体代码的书写如下我们对代码来进行一些分析hash[0]1对应第一个细节问题保证当整个区间的和为k时不会进行错误判断sum这个变量是用来替代前缀和数组的功能的在进行完每一次检查后更新一下哈希表中记录的信息6.和可被k整除的子数组题目来源974. 和可被 K 整除的子数组 - 力扣LeetCode这道题和和为k的那道题很像那道题求的是和为k的子数组这道题求的则是和可被k整除的数组因此大题的代码上不需要改变要变的只是哈希表增加数值的规则这道题需要注意的有两个点1.同余定理定理的内容假如a-b/kna-b的差能够整除k,那a%kb%k假设我们要求的是上图中sum-x那一部分那么sum-x%k0根据同余定理可以得到sum%kx%k这样就将问题转换为了在[0,i-1]这个区间找到前缀和/k的余数sum/k的余数的个数2.对取余的结果进行处理假如sum是一个负数那么sum%k的值也是一个负数为了让余数变为正数我们需要让sum%k的值加上k又为了防止对正数造成影响最后rsum%kk%k;代码如下7.连续数组题目来源525. 连续数组 - 力扣LeetCode先来讲暴力解法定义一个哈希表用来记录0和1的个数当两个相等时更新一下子数组的长度我们可以把这个题目转换一下将所有的0换成-1那么如果0和1的数目相等就相当于数组的和为0将问题转换为了找到和为0的最长的子数组这样一来这道题就跟之前的那道题十分相像了但是还有一些细节的问题需要更改之前那道题要求的是子数组的个数这道题要求的是子数组的长度那么我们哈希表中储存的数据的意义就需要进行更改了哈希表中储存的数据变成了前缀和为sum的最小下标并且我们更新hash表只需要记录一次就好了代码如下8.矩阵区域和题目来源1314. 矩阵区域和 - 力扣LeetCode我们结合图来分析一下题目的意思当k1时求ans[0][0],相当于要从0,0这个位置朝周围分别延伸1格然后将区域内的元素加起来得到的和就是ans[0][0]了依次类推我们可以借助二维前缀和来解决这道问题要求的ans数组元素就相当于要求右下角那一块元素的和转化为dp数组表示的话如下设区域左上角的点和右下角的点分别为x1y1x2y2ans[i][j]dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]dp[x1-1][y1-1]但由于我们之前学习的dp表是从1,1坐标开始的所以要对下标做一个变换各自都需要进行1并且dp表的行列都需要比mat表多一个代码如下以上就是本篇文章的全部内容了如果对你有帮助可以点个赞支持一下感谢各位的观看https://gitee.com/mo-ran-qingyun这是我个人的gitee仓库,账号上文章的代码都会发到仓库里有兴趣可以看一下