给定一个有序数组 s 和一个数 t,求数组中连续元素的和等于所给数的子数组。
如
s = [1,2,3,4,5,6,7]
t = 12
输出
[3,4,5]
如
s = [1,2,3,4,5,6,7]
t = 12
输出
[3,4,5]
|
lhx2008Mar 26, 2018 via Android
1
和 two-sum 排序版 解法一样,两个指针小了左边右移,大了右边左移就行
|
|
flyingpotMar 26, 2018 via iPhone
2
同向双指针?
|
|
binuxMar 26, 2018
4
不管怎么做都是 O(n) 的,对这种算法毫无兴趣。
|
|
mengyaoss77Mar 26, 2018
12
是滑动窗口吗
|
|
binuxMar 26, 2018
13
我被题目误导了,因为你这输出不唯一啊,但是没要求给出"所有"子数组啊
|
|
stevenbiptMar 26, 2018
14
瑟瑟发抖的萌新看着前面一群大佬在前排交流 (っ °Д °;)っ
|
|
qwsqwaMar 26, 2018 via Android
15
这道题基本算法就是双指针,复杂度 O(n),但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和,则必须遍历整个数组。 |
|
Justin13Mar 26, 2018 via Android
17
双指针,两头开始,求指针间数字的和,大了右边指针左移,小了双指针右移,对不对?
|
|
vegito2002Mar 26, 2018 via iPad
18
如果没有负数的话, 两个指针同时从左边走的滑动窗口应该可以;
各种楼上说的两头指针从左右两头走的方法没有理解具体怎么做。 |
|
akioMar 26, 2018
19
没有说是几个数呀,应该是滑动窗口吧
|
|
lhx2008Mar 26, 2018 via Android
20
@pwrliang 我当时想的是,a,b 指针,sum 值,b 先扫到尾部,不断累加 sum 值,再右移 a 或者左移 b,相应加减 sum。但是实际上的话,这样写会有点 bug,应该是个滑动窗口问题更加合适。
|
|
glasslionMar 26, 2018
21
@vegito2002
我想到的也是一头一尾两指针同事往右移, 先移尾,超过了则移头, 如此反复 |
|
findApr 1, 2018 via iPhone
22
target/2 然后从中间往两边走
|