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)，空間複雜度為常量