3sum 时间复杂度问题

zhuli19901106 发表于 2015-7-8 13:47
两份代码我都读了，感觉第一种更好。不过两份都有没找到bug，在lintcode上试了试也都ac了。
你是在leetc ...

第二种用hash的情况在leetcode上就超时了，不知道为什么

handsomecool 发表于 2015-7-8 15:07
呃，我发现我的旧code为啥超时了，因为我的算法错了囧。。。
我用的set去重元素，但元素可以重复用，改成m ...

意思是有很多重复的情况，都全部判断了一遍吗？所以超时了

caffery24 发表于 2015-7-8 21:44
意思是有很多重复的情况，都全部判断了一遍吗？所以超时了

应该是这样。比如[1 1 1 1 1 1 1 1 2 -3] 这个例子。本来找到第一个[1 2 -3]时，后面的1都可以直接跳过了。而第二段代码中还是坚持不懈地查询了后面的所有[1 2 -3]组合。两个代码最差时间复杂度一样，但是当有大量重复的时候，第一段代码事实上就接近O(N)了，而后者在任何情况下都是雷打不动的O(N^2)。而且第二段代码还创建了大量的不必要的ArrayList(即res)。我不知道垃圾回收的时间算不算在OJ的计时里，但是不管怎么说，这种本来不必要的创建-删除循环肯定会拖慢程序的效率。

caffery24 发表于 2015-7-8 21:43
第二种用hash的情况在leetcode上就超时了，不知道为什么

我是用C++写的，同样的方法。
于是java就是这么慢~常系数太大

求破 n2的解法, 造福全世界

readman 发表于 2015-7-8 23:25
求破 n2的解法, 造福全世界

你确定有更优复杂度的解？

zhuli19901106 发表于 2015-7-9 10:56
你确定有更优复杂度的解？

没, 等某人造福世界呢

readman 发表于 2015-7-9 11:58
没, 等某人造福世界呢

不如叫sharkwolf来试试，本版块数他最牛~