我感觉 LeetCode 上面对于代码的要求苛刻

V2EX = way to explore

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

现在注册

已注册用户请登录

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

新手,在leetcode上面做twosum.
第一次用迭代器
报错,超时
第二次用数组下标
报错,超时
要求苛刻我觉得很好!我会继续努力的.

leetcode

超时

下标

32 条回复 • 2015-02-16 12:05:09 +08:00

hcymk2

2015-02-13 15:05:05 +08:00

我用java刷完50%的题目还没碰到time out 这是 LeetCode在歧视java么？

ant_sz

2015-02-13 15:18:47 +08:00

two sum 应该可以用 O(nlogn) 的时间复杂度搞定。如果不是 O(nlogn) 过不了太正常了

exch4nge

2015-02-13 15:27:13 +08:00

确定你是用O(nlogn)或更小的时间复杂度搞定的，但还是超时的话，看看你是不是把自己调试打印的语句没注释掉……

binux

2015-02-13 15:27:38 +08:00

这。。LeetCode 上面的题都太简单了，完全是在考 bug free 而不是算法的。。

gandblack

2015-02-13 15:28:24 +08:00

不苛刻吧，话说Median of Two Sorted Arrays 写明要log(m+n)的时间复杂度，，你怎么破
或者two sum也写明要求 O(nlogn)的时间复杂度你就不会纠结下标还是迭代了

ivanlw

2015-02-13 15:36:35 +08:00

two sum 不是没有用O(n)做出来的面试直接刷掉吗？

caizixian

2015-02-13 15:52:34 +08:00

之前没细看做的一个
http://www.ivancai.me/2014/10/15/leetcode-two-sum.html

rangercyh

2015-02-13 15:56:34 +08:00

@binux 说的对，leetcode的题目确实不是考难度，而是考bug free，其实很适合算法新手做

caizixian

2015-02-13 15:57:16 +08:00

@wdy1184 其实我用的也是数组下标法，关键用了Python，就把dict当array用了下。

@binux @ivanlw 求看有无更好地实现

ivanlw

2015-02-13 16:07:01 +08:00

@caizixian 利用不同编程语言的hash set类型（不同语言有不同的叫法，C++是#include <unordered_set>，Java和Python的麻烦自己找一下）的look up time是O(1)的特性，跑一次就行了，举个例子吧(2, 7, 11, 15)找22：

定义一个hashset就暂时叫a吧，一开始a是空的；先跑到2，找一下a里面有没有22-2=20（时间O(1)）, 没有，把2存进a；然后7，找一下a里面有没有22-7=15，没有，把7存进去；跑到11，找一下a里面有没有22-11=11，没有把11存进去；跑到15，找一下a里面有没有22-15=7，有，所以两个数字就是7和15

caizixian

2015-02-13 16:09:26 +08:00

@ivanlw 我就是这么写的。不过这样算作弊吧

gandblack

2015-02-13 16:34:08 +08:00

@ivanlw 不是O(n)直接刷掉？有没有这么狠。。。。求一个时间空间复杂度都O(n)的解法

wilsoncao

2015-02-13 17:23:12 +08:00

@binux @rangercyh 我觉得bug free就很难了。。。

DaniloSam

2015-02-13 17:39:21 +08:00

```python
class Solution:
# @return a tuple, (index1, index2)
def twoSum(self, num, target):
result = {}
for i, n in enumerate(num, 1):
if target - n not in result:
result[n] = i
else:
return result[target - n], i

return ()
```

用hash table，O(n)啊不会超时啊

JackWindows

2015-02-13 19:28:20 +08:00

@binux 说出了我的心声。各位大神如果真想锻炼的话去做noi.openjudge.cn吧

GtDzx

2015-02-13 19:44:58 +08:00

@JackWindows 赞！没想到还有人知道noi.openjudge.cn这个题库。这个题库完成的话应该是很好的练习去处。

twistoy

2015-02-13 19:47:33 +08:00

@JackWindows OIer？

udonmai

2015-02-13 21:59:30 +08:00

每个人随便交个最 naive 的方法就过了，leetcode 也就没存在的必要了。。所以它多卡一点时间太正常了。。再者，你随便写了个方法想都不想就过了，你能学到什么。。

wdy1184

2015-02-13 22:19:03 +08:00

@DaniloSam 我用的是C++，不要剧透哦，我想自己来~

wdy1184

2015-02-13 22:19:34 +08:00

@hcymk2 没用java，可能java有更好的方法吧

phoeagon

2015-02-13 22:26:11 +08:00

@ivanlw 要排序啊。

phoeagon

2015-02-13 22:26:27 +08:00

@JackWindows 去spoj!

ember

2015-02-13 23:03:02 +08:00

@GtDzx 卧槽惊现轩哥

ivanlw

2015-02-14 07:50:19 +08:00 via iPhone

@phoeagon 排序就至少O(nlogn)，比这样子慢

phoeagon

2015-02-14 09:06:03 +08:00

@ivanlw 你可以用hash table我就基数排序！

bugcoder

2015-02-14 21:53:27 +08:00

@ivanlw
@caizixian
@phoeagon
hashset 不行，输入里面有重复的元素

bugcoder

2015-02-14 21:57:11 +08:00

@DaniloSam
测试数据里面有： [0,4,3,0], 0
要求答案是唯一的

bugcoder

2015-02-14 22:07:39 +08:00

class Solution:

# @return a tuple, (index1, index2)
def twoSum(self, num, target):
sumlen = len(num)
for reverseindex in range(sumlen):
sub = target - num.pop()
if sub in num:
return (num.index(sub)+1, sumlen-reverseindex)

通过了，不过感觉不是最好的

bugcoder

2015-02-14 22:13:07 +08:00

@DaniloSam
为什么python code的格式都没有了呢，难道只能楼主才能保持格式？

DaniloSam

2015-02-15 08:54:12 +08:00 via iPhone

@bugcoder 要贴gist看来

我这么写答案是唯一啊，返回应该是1,4，这个case怎么了

wdy1184

2015-02-16 12:02:49 +08:00

果然要用hash表,不太会算时间复杂度,只是知道了这个是O(n)的复杂度.

wdy1184

2015-02-16 12:05:09 +08:00

@ant_sz 我用了,先排序,再找,可是要返回的是数组的下标,所以这个不管用