c********p
发帖数: 1969 | 1 我只能一个一个的试，这个题array先排序了貌似也没用吧？
虽然我还是先排序了。。。
O(n^3)，有更好的方法么？ | e*******8
发帖数: 94 | | c********p
发帖数: 1969 | | m********2
发帖数: 89 | | e*******8
发帖数: 94 | 5 inner loop已经是线性复杂度了呀，用binary search反而会增加时间复杂度？而且３
sum的时间复杂度的lower bound不是已经是Omega(n^2)了么
【在 m********2 的大作中提到】
: inner loop 可以换成 binary search?
| w****g
发帖数: 727 | 6 若是要求找出一组解，而不是所有解，貌似lower bound是open problem
【在 e*******8 的大作中提到】
: inner loop已经是线性复杂度了呀，用binary search反而会增加时间复杂度？而且３
: sum的时间复杂度的lower bound不是已经是Omega(n^2)了么
| e*******8
发帖数: 94 | 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
| w****g
发帖数: 727 | 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)个
|
|
