1
lhx2008 2018-03-26 09:19:19 +08:00 via Android
和 two-sum 排序版 解法一样,两个指针小了左边右移,大了右边左移就行
|
2
flyingpot 2018-03-26 09:19:19 +08:00 via iPhone
同向双指针?
|
4
binux 2018-03-26 09:22:17 +08:00
不管怎么做都是 O(n) 的,对这种算法毫无兴趣。
|
12
mengyaoss77 2018-03-26 09:58:02 +08:00
是滑动窗口吗
|
13
binux 2018-03-26 10:00:45 +08:00
我被题目误导了,因为你这输出不唯一啊,但是没要求给出"所有"子数组啊
|
14
stevenbipt 2018-03-26 10:27:06 +08:00
瑟瑟发抖的萌新看着前面一群大佬在前排交流 (っ °Д °;)っ
|
15
qwsqwa 2018-03-26 10:36:56 +08:00 via Android
这道题基本算法就是双指针,复杂度 O(n),但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和,则必须遍历整个数组。 |
17
Justin13 2018-03-26 11:20:21 +08:00 via Android
双指针,两头开始,求指针间数字的和,大了右边指针左移,小了双指针右移,对不对?
|
18
vegito2002 2018-03-26 11:30:28 +08:00 via iPad
如果没有负数的话, 两个指针同时从左边走的滑动窗口应该可以;
各种楼上说的两头指针从左右两头走的方法没有理解具体怎么做。 |
19
akio 2018-03-26 11:37:56 +08:00
没有说是几个数呀,应该是滑动窗口吧
|
20
lhx2008 2018-03-26 11:54:59 +08:00 via Android
@pwrliang 我当时想的是,a,b 指针,sum 值,b 先扫到尾部,不断累加 sum 值,再右移 a 或者左移 b,相应加减 sum。但是实际上的话,这样写会有点 bug,应该是个滑动窗口问题更加合适。
|
21
glasslion 2018-03-26 14:33:09 +08:00
@vegito2002
我想到的也是一头一尾两指针同事往右移, 先移尾,超过了则移头, 如此反复 |
22
find 2018-04-01 10:34:18 +08:00 via iPhone
target/2 然后从中间往两边走
|