Asking about O(logN) solution.


  • 3
    F

    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)?


  • 6
    L

    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?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.