lintcode 404有人能指教一下吗

subarray-sum-ii
https://www.lintcode.com/problem/subarray-sum-ii/

双指针的O(n)解法，想不明白。

我过去用的Binary Search。

O（N）的想法应该是先计算prefixsum，
针对任何一个[ i ]，维护一个 j, k 使得 [ i ]到任何j k之间都可以符合要求的range。res+=k-j+1
下次迭代，移动i++
这必然会要求检查j是否符合，然后检查k是否符合
如果j超出了len(A)则搜索停止。

你可以参考网上的题解
比如https://blog.csdn.net/roufoo/article/details/88773399
题目里说数组里的所有数都是正数 所以前缀和是递增的
前缀和presum[]
如果有指针i j且i<=j
如果区间(i,j)符合条件 那么区间(i,[j~len])都符合条件
所以先固定i 通过调整j得到一个最小的区间然后计算个数 再增加i再调整
大致是这么个意思

onewaymyway 发表于 2019-9-13 22:18
你可以参考网上的题解
比如https://blog.csdn.net/roufoo/article/details/88773399
题目里说数组里的所 ...

对每个presum找出符合条件的i,j答案res不是会重复加之前已经加过的subarray了吗？

whodatj 发表于 2019-9-13 23:08
对每个presum找出符合条件的i,j答案res不是会重复加之前已经加过的subarray了吗？

presum只是为了计算方便
i,j
其中i表示当前subarray起点 j表示终点
固定起点i 通过调整终点j得到最小的以i为起点的符合条件的 然后终点从j到len都是符合条件 所以加上这些个数
然后起点i++再调整j再计算

14417335 发表于 2019-9-13 21:48
我过去用的Binary Search。

O（N）的想法应该是先计算prefixsum，

那么到下一个 i 的时候，res+=k-j+1里面为什么不会重复计算上一次循环已经加过的SUM了？

whodatj 发表于 2019-9-13 16:41
那么到下一个 i 的时候，res+=k-j+1里面为什么不会重复计算上一次循环已经加过的SUM了？

因为以ℹ️开始的subarray是unique的。所以即便有些j和k间和上次ℹ️的j和k间有overlap，仍然是题目所要求的

14417335 发表于 2019-9-14 08:36
因为以ℹ️开始的subarray是unique的。所以即便有些j和k间和上次ℹ️的j和k间有ov ...

明白了，谢谢！

大米 ++++

onewaymyway 发表于 2019-9-13 22:18
你可以参考网上的题解
比如https://blog.csdn.net/roufoo/article/details/88773399
题目里说数组里的所 ...

哈，发现我的博客被引用了。