2018026 今日算法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2461 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

输出
[3,4,5]

子数组

给定

算法

有序

22 条回复 • 2018-04-01 10:34:18 +08:00

lhx2008

2018-03-26 09:19:19 +08:00 via Android

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

flyingpot

2018-03-26 09:19:19 +08:00 via iPhone

同向双指针？

gbin

2018-03-26 09:20:27 +08:00 via Android

@lhx2008 老哥手法老练👍

binux

2018-03-26 09:22:17 +08:00

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

binux

2018-03-26 09:23:52 +08:00

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

gbin

2018-03-26 09:23:55 +08:00 via Android

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

muziki

2018-03-26 09:27:45 +08:00

@gbin 这位是 python 巨佬

binux

2018-03-26 09:28:31 +08:00

@gbin 超偏门的算法。

hanzichi

2018-03-26 09:44:04 +08:00

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

binux

2018-03-26 09:50:41 +08:00

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

binux

2018-03-26 09:52:08 +08:00

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

mengyaoss77

2018-03-26 09:58:02 +08:00

是滑动窗口吗

binux

2018-03-26 10:00:45 +08:00

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

stevenbipt

2018-03-26 10:27:06 +08:00

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

qwsqwa

2018-03-26 10:36:56 +08:00 via Android

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

pwrliang

2018-03-26 11:14:10 +08:00

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

Justin13

2018-03-26 11:20:21 +08:00 via Android

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

vegito2002

2018-03-26 11:30:28 +08:00 via iPad

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

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

akio

2018-03-26 11:37:56 +08:00

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

lhx2008

2018-03-26 11:54:59 +08:00 via Android

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

glasslion

2018-03-26 14:33:09 +08:00

@vegito2002
我想到的也是一头一尾两指针同事往右移，先移尾，超过了则移头，如此反复

find

2018-04-01 10:34:18 +08:00 via iPhone

target/2 然后从中间往两边走