LeetCode 新题 Two Sum II 求最佳解

题目 ：Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

是之前 two sum 的 fllow up question, 但是这次是given an array is already sorted in ascending order. 想尝试 O(log n)的时间做出来。但始终做不出来。有大神有想法吗？

xzt8350 发表于 2015-1-8 05:59
You may assume that each input would have exactly one solution. 题目说只有一个解。。 我也只能想出  ...

呃，写的时间太长了，忘了。这题当时倒是写过一个binary search的，但是感觉runtime是O(nlogn+n)。就是用BS左右找数，没有就换方向，缩小范围。

O(n)就最好了.

希望找到两个数加起来=0... 并且我们还有extra information... 负数和正数的分割点在哪里...
那么问题等同于给两个sorted array, 找里面有没有相同的数字(把其中的负数array反过来...)

然后可用adversary argument证明这个要O(n)时间.

c__jay 发表于 2015-1-10 12:41
其实我经常都很不理解，因为实际应用情况下只要做一个table就能一劳永逸，当然我知道其实是偏题了- -因为 ...

没有动态输入吧，就是给你一个array。做table需要额外的空间，但是如果2个指针往中间移的话不需要

感觉就是O(n)，因为他要的是全部解，只不过省空间了。

王可雪 发表于 2015-1-8 05:57
感觉就是O(n)，因为他要的是全部解，只不过省空间了。

You may assume that each input would have exactly one solution. 题目说只有一个解。。 我也只能想出 O(n)

我粗想了一下，应该没有O(logn)的解。因为要是想O(logn)大概就需要二分，但是这个题目里你没法保证每次去掉的那一半里没有正解需要的数。
比如数是12346，sum是5。先看1+6=7比5大，然后看1+3，比5小。现在问题来了。是选择2+3还是1+4？所以。。。

yxyxyx 发表于 2015-1-8 06:11
我粗想了一下，应该没有O(logn)的解。因为要是想O(logn)大概就需要二分，但是这个题目里你没法保证每次去掉 ...

你这个例子不成立 题目中说每组数只有一组解

既然already sorted就直接用Two pointers从两头开始往中间找

xzt8350 发表于 2015-1-7 19:56
你这个例子不成立 题目中说每组数只有一组解

那样就12478，然后sum是6.
还是一样的问题，1+8比6大，于是看中间的数，1+4比6小。要是从二分的角度去做下一步就应该是看4和7，这显然是不对的，因为答案是2和4.

把全部和做成一个table然后再查？不过不知道求和的过程要不要算进时间就是了

c__jay 发表于 2015-1-10 12:14
把全部和做成一个table然后再查？不过不知道求和的过程要不要算进时间就是了

这个肯定要算的吧...