一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2753|回复: 17
收起左侧

[Leetcode] LeetCode 新题 Two Sum II 求最佳解

[复制链接] |试试Instant~ |关注本帖
xzt8350 发表于 2015-1-8 05:44:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x


题目 :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)的时间做出来。但始终做不出来。有大神有想法吗?

王可雪 发表于 2015-1-8 05:57:14 | 显示全部楼层
感觉就是O(n),因为他要的是全部解,只不过省空间了。
回复 支持 反对

使用道具 举报

 楼主| xzt8350 发表于 2015-1-8 05:59:23 | 显示全部楼层
王可雪 发表于 2015-1-8 05:57
感觉就是O(n),因为他要的是全部解,只不过省空间了。

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

使用道具 举报

王可雪 发表于 2015-1-8 06:08:46 | 显示全部楼层
本帖最后由 王可雪 于 2015-1-8 06:58 编辑
xzt8350 发表于 2015-1-8 05:59
You may assume that each input would have exactly one solution. 题目说只有一个解。。 我也只能想出  ...

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

使用道具 举报

yxyxyx 发表于 2015-1-8 06:11:02 | 显示全部楼层
我粗想了一下,应该没有O(logn)的解。因为要是想O(logn)大概就需要二分,但是这个题目里你没法保证每次去掉的那一半里没有正解需要的数。
比如数是12346,sum是5。先看1+6=7比5大,然后看1+3,比5小。现在问题来了。是选择2+3还是1+4?所以。。。
回复 支持 反对

使用道具 举报

 楼主| xzt8350 发表于 2015-1-8 07:56:12 | 显示全部楼层
yxyxyx 发表于 2015-1-8 06:11
我粗想了一下,应该没有O(logn)的解。因为要是想O(logn)大概就需要二分,但是这个题目里你没法保证每次去掉 ...

你这个例子不成立 题目中说每组数只有一组解
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2015-1-9 01:13:47 | 显示全部楼层
既然already sorted就直接用Two pointers从两头开始往中间找
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2015-1-9 02:45:36 | 显示全部楼层
xzt8350 发表于 2015-1-7 19:56
你这个例子不成立 题目中说每组数只有一组解

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

使用道具 举报

c__jay 发表于 2015-1-10 12:14:51 | 显示全部楼层
把全部和做成一个table然后再查?不过不知道求和的过程要不要算进时间就是了
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-1-10 12:16:58 | 显示全部楼层
c__jay 发表于 2015-1-10 12:14
把全部和做成一个table然后再查?不过不知道求和的过程要不要算进时间就是了

这个肯定要算的吧...
回复 支持 反对

使用道具 举报

c__jay 发表于 2015-1-10 12:41:51 | 显示全部楼层
wenqiang88 发表于 2015-1-10 12:16
这个肯定要算的吧...

其实我经常都很不理解,因为实际应用情况下只要做一个table就能一劳永逸,当然我知道其实是偏题了- -因为题目要的是动态输入,但是总是不自觉的香道这个,偶真是太小家子气了...
回复 支持 反对

使用道具 举报

wilsoj 发表于 2015-1-10 18:41:50 | 显示全部楼层
用hash map呢?
回复 支持 反对

使用道具 举报

wilsoj 发表于 2015-1-10 18:41:56 | 显示全部楼层
用hash map呢?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-1-10 21:38:07 | 显示全部楼层
c__jay 发表于 2015-1-10 12:41
其实我经常都很不理解,因为实际应用情况下只要做一个table就能一劳永逸,当然我知道其实是偏题了- -因为 ...

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

使用道具 举报

wenqiang88 发表于 2015-1-10 21:38:13 | 显示全部楼层
c__jay 发表于 2015-1-10 12:41
其实我经常都很不理解,因为实际应用情况下只要做一个table就能一劳永逸,当然我知道其实是偏题了- -因为 ...

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

使用道具 举报

qashtishi 发表于 2015-1-11 15:39:46 | 显示全部楼层
到底是怎么解决的呀?
回复 支持 反对

使用道具 举报

mgccl 发表于 2015-1-11 18:13:36 | 显示全部楼层
本帖最后由 mgccl 于 2015-1-11 18:35 编辑

O(n)就最好了.

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

然后可用adversary argument证明这个要O(n)时间.
回复 支持 反对

使用道具 举报

葛相辰 发表于 2015-1-21 05:17:09 | 显示全部楼层
我不是很懂map的工作原理。但是这题用map来做,就是把index和value 来map起来,利用map的查找时间可以达到o(n)的时间对吧。如果这样的话,可不可以用二分法查找结合map的查找时间来完成呢?这只是一个大体思路。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 07:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表