I have seen some discussions in the discussion session about the binary search idea. Even though, they all look better ideas than two pointers, they still need O(N) in the worse case.
I am asking is there any idea to solve this question in completely O(logN)?
if we can solve 2sum in log(n), we can solve 3sum in nlog(n). However, until 2014, the best we achieve is O(n^2/(logn/loglogn)^(2/3)) according to wikipedia. So I don't think it is possible, right?
@lzhen Not sure about the binary search algorithm, but your argument is not true. Numbers are sorted in the problem.