2018026 今日算法

[gbin]

给定一个有序数组 s 和一个数 t，求数组中连续元素的和等于所给数的子数组。

如
s = [1,2,3,4,5,6,7]
t = 12

输出
[3,4,5]

[lhx2008]

和 two-sum 排序版 解法一样，两个指针小了左边右移，大了右边左移就行

[flyingpot]

同向双指针？

[gbin]

@lhx2008 老哥手法老练👍

[binux]

不管怎么做都是 O(n) 的，对这种算法毫无兴趣。

[binux]

@binux 哦，确实可以 O(logn) 的。不过还是挺无趣的。

[gbin]

@binux 允许我大胆猜测一下，你是算法岗?

[muziki]

@gbin 这位是 python 巨佬

[binux]

@gbin 超偏门的算法。

[hanzichi]

@binux O(logn) 能解？求指导

[binux]

@hanzichi 反正数组有序，和它左右两边相加也是有序的，二分就好了嘛。

[binux]

@hanzichi 不过经你这么一说，好像没有规定连续的个数啊。。尴尬

[mengyaoss77]

是滑动窗口吗

[binux]

我被题目误导了，因为你这输出不唯一啊，但是没要求给出"所有"子数组啊

[stevenbipt]

瑟瑟发抖的萌新看着前面一群大佬在前排交流 (っ °Д °;)っ

[qwsqwa]

这道题基本算法就是双指针，复杂度 O(n)，但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和，则必须遍历整个数组。

[pwrliang]

@lhx2008 您好，那个 sorted 2 sum 我做出来了，您能说下这个 n-sum 问题怎么解吗，谢谢？

[Justin13]

双指针，两头开始，求指针间数字的和，大了右边指针左移，小了双指针右移，对不对?

[vegito2002]

如果没有负数的话， 两个指针同时从左边走的滑动窗口应该可以；

各种楼上说的两头指针从左右两头走的方法没有理解具体怎么做。

[akio]

没有说是几个数呀，应该是滑动窗口吧

[lhx2008]

@pwrliang 我当时想的是，a,b 指针，sum 值，b 先扫到尾部，不断累加 sum 值，再右移 a 或者左移 b，相应加减 sum。但是实际上的话，这样写会有点 bug，应该是个滑动窗口问题更加合适。