LeetCode-3Sum Closest

https://oj.leetcode.com/problems/3sum-closest/

和3sum非常类似，基本重用代码就行。

区别在于，如果找到target，可以直接返回，并且需要维护一个目前最小差别的和值。

代码如下：

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int dif = Integer.MAX_VALUE;
        int rst = 0;
        if(num==null || num.length<3) return rst;
        Arrays.sort(num);
        for(int i=0; i<num.length; i++){
            int start = i+1;
            int end = num.length-1;
            int intarget = target-num[i];
            while(start<end){
                int sum= num[start]+num[end];
                int thisdif = Math.abs(sum+num[i]-target);
                if(thisdif<dif){
                    dif = thisdif;
                    rst = sum+num[i];
                }
                if(sum<intarget){
                    start++;
                } 
                else if(sum>intarget){
                    end--;
                } 
                else{
                    return target;
                }
            }
        }
        return rst;
    }
}
           

时间复杂度跟3sum一样，都是O(n^2)，空间复杂度为常量