Could it be O(nlgn)?


  • 1
    L

    First, do a quick sort or merge sort on the array. Then set the two pointers to the first and the last element. Check the numbers in-between and calculate new sums and delta by binary search. After that move the two pointers according to the value of della.

    The sort takes (O(nlgn)), the outer loop for two pointers takes O(n) and testing numbers in-between takes O(lgn), so total should be O(nlgn).

    Following is my code:

    public int threeSumClosest(int[] num, int target) {
        if (num == null || num.length <=2) return Integer.MIN_VALUE;
        int i = 0, j = num.length - 1, delta = Integer.MAX_VALUE;
        Arrays.sort(num);
        while(i+1<j){
            delta = checkSum(num, i, j, target, delta);
            if (delta > 0)
                --j;
            else if (delta < 0)
                ++i;
            else
            	break;
        }
        return target + delta; 
    }
    
    public int checkSum(int[] num, int left, int right, int target, int delta){
        int lnum = num[left], rnum = num[right];
        ++left; --right;
        int mid;
        while(left <= right){
        	mid = (left+right)/2;
            int sum = lnum + rnum + num[mid];
            if (Math.abs(sum-target) < Math.abs(delta))
                delta = sum - target;
            if (sum > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return delta;
    }

  • 0
    C

    Is it guarenteed that your lnum + rnum + num[mid] is the median of all the three-sums?
    So far I cannot see it.


  • 0
    L

    checkSum() is designed to find the minimum delta given the "fixed" lnum and rnum, i.e. seek a number between lnum and rnum (exclusive) which makes the sum closest to the target.

    A straightforward approach is to test all numbers in-between one by one. But since the array has been sorted, we can use binary search: if the sum of lnum, rnum and the current median is greater than target, we can try the numbers smaller than the median, or the numbers larger than the median. It guarantees we are always testing the the sum closer to the target.


  • 0
    S

    Great viewpoint.


  • 1
    O

    There are some special cases, like:
    [-8, -1, ......, 5, 6], target=0.
    (-8)+(-1)+6-0=-3, while (-8)+5+6-0=3.
    The absolute values are equal, so the delta can be positive or negative.
    ++i or --j in this situation?


  • 12
    K

    the fact that the closest sum in range [i, j] is less than target does not mean that a closer sum must be in range [i+1, j].

    consider this case: target=150, num[]={0, 5, 50, 100, 140}

    the closest sum in range [0, 4] is 0+5+140=145 and it's less than 150, so your code will go on with range [1, 4]. However, the closest sum is in range [0, 3] and it's 0+50+100=150.


  • 0
    S
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 1
    S

    The problem is that we cannot move the pointer one way or the other based on the values of delta . So if you want to you use binary search(O(logn)) for the third element , you need to to do it for all the possible pairs(O(n^2)) . So the algorithm becomes O(n^2 logn).


Log in to reply
 

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