基础算法(十) -- 前缀和

[@yayayu2bee131]

谢谢古城。 34:46的lazy propagation应该是： [1,3,2] => [0,2,0,0,-2] [2,4,3] => [0,2,3,0,-2] (因为end的index是最后一位，所以value加3后不用在不存在的下一步取反) [0,2,-2] => [-2,2,3,2,-2]

[@古城算法]

赞，感谢分析，我看了下ppt里面好像是只写了前2步之后的变化结果来做举例

[@刷个题]

感谢留言 我发现ppt 上右下角写的例子是对的。[1,3,2], [2, 3, 3] 就是城主讲的时候讲的例子不是PPT右下角的例子，而是力扣本身的那个例子。

[@刷个题]

讲得真棒呀，每次都会点赞！

[@Grace0720mcy]

13:37 LC 560 非常经典 15:06 LC 560 暴力解 16:04 LC 560 最优解

[@xiongli7070]

举报了举报了，讲的也太好了，这讲课又有趣质量又高，搞的老是想看古城的解法了（手动狗头

[@Angel-bw2lb]

醍醐灌顶！！！

[@BullishBuddy]

Edie 讲的好！不错！

[@yutianzhang6058]

974 Subarray Sums Divisible by K这题。如果没做过这题，在面试的时候我能做出O(n^2)的解，但是基本想不到“相同余数再次出现，ij之间的subarray和一定可以被整除”这种特性，也做不出来O(n)的解。

[@古城算法]

这个就是2sum的变种。类似dp cache的性质找之前已经计算过的值来减少重复计算。多看一些2 sum我们也有专题就熟悉了。

[@NatPersea05]

这集内容真棒，古城哥哥辛苦了

[@古城算法]

感谢支持哈哈哈！

[@刷个题]

862有疑问：用滑动窗口的视角来看，i是右指针，单调队列中保存的是左指针，可以理解为什么在满足答案的时候要popFirst, 讲得很清楚。没有想通为什么在queue可以保持单调递增，这样不会漏掉答案吗？

[@saitmesutcanilhaner8850]

谢谢！！

[@wl7497]

古城 发现一处小错误 523这里的map的键值对应该是

[@古城算法]

对滴，good catch, 哈哈哈注释写反了

[@nanliang2237]

oh no, 轻松愉快的星期五

[@sinco1042]

讲的真好，“古城算法”，是不是pingyao的？>_

[@古城算法]

哈哈哈，山西老乡啊，不是哦

[@hacksbsb]

咱们古城哥哥太帅太牛了

[@古城算法]

感谢支持，不帅不帅一般般哈哈哈

[@DED_Search]

42:10 老师太可爱了 😂

[@古城算法]

哈哈哈哈😁

[@weiyao806]

862 这个维持递增单调性是不是因为k > 0? 否则的话，这样的queue做不了？

[@古城算法]

感觉这个和queue是一样的把，对于deque来说。 请问你的意思是？ 因为有负数，所以不能移动window左指针，需要移动prefix左指针

[@weiyao806]

@@古城算法 我的意思是因为K是正数，所以可以用单调递增的queue，否则如果K是任意整数，那么这个方法似乎不行。

[@古城算法]

@@weiyao806 请问你说的是负整数k嘛？那就当正整数k做？先把所有数字的符号反一下？

[@zlmsailor]

@@weiyao806 如果k是负数，感觉题目没有意义了，直接line scan就可以了。分两种情况： 1，input array全是负数，负数加负数更负，return 只能是1或者不存在。 2，input array至少有一个正数，那么直接 return 1，因为任意一个正数大于k。

[@user-abcdexyz]

862，leetcode 好像更新了test case，现在sum数组如果用int会越界。

[@古城算法]

对的，后来好多必须用long了呢。

[@yizhewu4249]

楼主是山西人嘛 哈哈哈哈哈

[@古城算法]

对呀，哈哈哈

[@yizhewu4249]

@@古城算法 哈哈哈哈 我昨天第一次看 一听就是

[@yizhewu4249]

@@古城算法 我是太原的