3sum closest哪个解法最优？# JobHunting - 待字闺中
c*p
1 楼
我只能一个一个的试，这个题array先排序了貌似也没用吧？
虽然我还是先排序了。。。
O(n^3)，有更好的方法么？
虽然我还是先排序了。。。
O(n^3)，有更好的方法么？
c*p
3 楼
谢谢，捧回去看看！
【在 e*******8 的大作中提到】
: O(n^2)
: http://stackoverflow.com/questions/2070359/finding-three-elemen
【在 e*******8 的大作中提到】
: O(n^2)
: http://stackoverflow.com/questions/2070359/finding-three-elemen
m*2
4 楼
inner loop 可以换成 binary search?
【在 e*******8 的大作中提到】
: O(n^2)
: http://stackoverflow.com/questions/2070359/finding-three-elemen
【在 e*******8 的大作中提到】
: O(n^2)
: http://stackoverflow.com/questions/2070359/finding-three-elemen
e*8
5 楼
inner loop已经是线性复杂度了呀，用binary search反而会增加时间复杂度？而且３
sum的时间复杂度的lower bound不是已经是Omega(n^2)了么
【在 m********2 的大作中提到】
: inner loop 可以换成 binary search?
sum的时间复杂度的lower bound不是已经是Omega(n^2)了么
【在 m********2 的大作中提到】
: inner loop 可以换成 binary search?
w*g
6 楼
若是要求找出一组解，而不是所有解，貌似lower bound是open problem
【在 e*******8 的大作中提到】
: inner loop已经是线性复杂度了呀，用binary search反而会增加时间复杂度？而且３
: sum的时间复杂度的lower bound不是已经是Omega(n^2)了么
【在 e*******8 的大作中提到】
: inner loop已经是线性复杂度了呀，用binary search反而会增加时间复杂度？而且３
: sum的时间复杂度的lower bound不是已经是Omega(n^2)了么
e*8
7 楼
３sum本来就是只需要找一组解吧？如果要把所有的解都找出来，很容易构造Omega(n^2
)的例子吧：比如 S = {1,2,...,n, -3,-4,...,1-2n}, |S|=3n-3, 但是满足a+b+c=0的
解有C(n,2)个
【在 w****g 的大作中提到】
: 若是要求找出一组解，而不是所有解，貌似lower bound是open problem
)的例子吧：比如 S = {1,2,...,n, -3,-4,...,1-2n}, |S|=3n-3, 但是满足a+b+c=0的
解有C(n,2)个
【在 w****g 的大作中提到】
: 若是要求找出一组解，而不是所有解，貌似lower bound是open problem
w*g
8 楼
then an open problem
^2
【在 e*******8 的大作中提到】
: ３sum本来就是只需要找一组解吧？如果要把所有的解都找出来，很容易构造Omega(n^2
: )的例子吧：比如 S = {1,2,...,n, -3,-4,...,1-2n}, |S|=3n-3, 但是满足a+b+c=0的
: 解有C(n,2)个
^2
【在 e*******8 的大作中提到】
: ３sum本来就是只需要找一组解吧？如果要把所有的解都找出来，很容易构造Omega(n^2
: )的例子吧：比如 S = {1,2,...,n, -3,-4,...,1-2n}, |S|=3n-3, 但是满足a+b+c=0的
: 解有C(n,2)个
相关阅读
求 VMware 面经。。谢谢。。google的机会关于reference check水果vs一百二十六请问现在Apple 什么package? (转载)pocket gems电面第二轮面经请教cs大牛湾区公司招power electronics背景的test engineer (转载)apple供应链死了一个中国人？H-1B六年到期了，perm还没下。这可怎么办阿？ (转载)求Facebook，dropbox，pinterest 内推Cisco一轮on campus给offerGithub，Sourceforge开源贡献对找工作的帮助有没有人面过citrix？顺便也求网上面试经验请问OPT EAD卡上标有地址吗?请教下转身份的问题， H1->F2->F1求software engineer 内推fb电面面经本屌学过的最难的课发包子,求解读, HR的信是啥意思啊? a firm update