3Sum Closest

3Sum Closest

 

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 

Naive Way: 我一开始想了一个binary search 的办法，先把数组排序，每次取一头(i)一尾(j)，在中间

找最接近x = target-num[i]-num[j]的数，如果得到的和num[i]+num[j]+num[x]小于target,说明

要增加sum，i++,否则就要减小sum,j--。这个方法只需要O(nlogn)的时间。

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        Arrays.sort(num);
        int min = Integer.MAX_VALUE;
        int rlst = target;
        int i = 0, j = num.length-1;
        while(i+1 < j){
            int rest = target-num[i]-num[j];
            int x = binarySearch(num, i+1, j-1, rest);
            int sum = num[i]+num[j]+num[x];
            if(sum==target){return target;}
            if(sum < target)
                i++;
            else
                j--;
            if(Math.abs(sum-target) < min){
                min = Math.abs(sum-target);
                rlst = sum;
            }
        }
        return rlst;
    }   

    private int binarySearch(int num[], int begin, int end, int t){
        int middle = begin;
        if(t > num[end]){return end;}
        if(t < num[begin]){return begin;}
        while(begin < end){
            middle = (begin+end)/2;
            if(num[middle]==t)
                break;
            if(num[middle] < t)
                begin = middle+1;
            if(num[middle] > t)
                end = middle-1;
        }
        return Math.abs(num[middle]-t) >= Math.abs(num[middle+1]-t)?middle+1:middle;
    }
} 

这个方法可以通过OJ，但是这个方法是错的，在Discuss上居然有人跟我想了同一个方法，并且有别人提出了质疑，举出了
[0 5 50 100 140] 150, 这个例子， 这个例子说明了即使当前和小于target，也不一定要增加序数而有可能要减小序数，因为前后两次binary search得到的数会不一样。于是这个O(nlogn)的方法宣告失败。

Improved Way:从头开始想，brute force 需要O(n^3)，那么应该在O(n^2)或者O(n^2 logn)内解决。3-sum就可以O(n^2)解决，但是这次不能确切找一个数，用set先存起来没什么用作。根据之前的方案，通过O(n^2)可以遍历所有两个数的组合，那么可以通过O(logn)的 binary search找最接近的数，这样下来算法就是O(n^2 logn)，这样的方法我试了试，是可以通过的，而且运行时间并不慢。

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        Arrays.sort(num);
        int min = Integer.MAX_VALUE;
        int rlst = target;
        for(int i = 0;i < num.length-2;i++){
            for(int j = num.length-1; j >= i+2;j--){
                int rest = target-num[i]-num[j];
                int x = binarySearch(num, i+1, j-1, rest);
                int sum = num[i]+num[j]+num[x];
                if(Math.abs(sum-target) < min){
                    min = Math.abs(sum-target);
                    rlst = sum;
                }
            }
        }
        return rlst;
    }
    
    private int binarySearch(int num[], int begin, int end, int t){
        int middle = begin;
        if(t > num[end]){return end;}
        if(t < num[begin]){return begin;}
        while(begin < end){
            middle = (begin+end)/2;
            if(num[middle]==t)
                break;
            if(num[middle] < t)
                begin = middle+1;
            if(num[middle] > t)
                end = middle-1;
        }
        return (begin+end)/2;
    }
}


Discuss中有唯一一种O(n^2)的方法，用了3sum一模一样的策略。原来觉得很厉害，现在觉得好像谁都会了。


public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num.length < 3){return 0;}
        int closest = num[0]+num[1]+num[2];
        int dis = Math.abs(closest-target);
        Arrays.sort(num);
        for(int i = 0;i < num.length-2;i++){
            // set two pointers, one from small-end, one from large-end
            int p = i+1;
            int q = num.length-1;
            while(p < q){
                int sum = num[i]+num[p]+num[q];
                if(Math.abs(sum-target) < dis){
                    closest = sum;
                    dis = Math.abs(sum-target);
                }
                if(sum > target)
                    q--;
                if(sum < target)
                    p++;
                if(sum == target)
                    return sum;
            }
        }
        return closest;
    }
}