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

// 2/18/2014 code rewrite

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if (num==null||num.length==0){
            return -1;
        }
        int result=0;
        int minDif=Integer.MAX_VALUE;
        Arrays.sort(num);
        
        for (int i=0; i<num.length-2; i++ ){
            
            
            int first=num[i];
            int left=i+1;
            int right=num.length-1;
            
            while (left<right){
              int value=first+num[left]+num[right];
              if (value==target){
                  return value;
              }
              int diff=Math.abs(value-target);
              if (diff<minDif){
                  result=value;
                  minDif=diff;
              }
              
              if (value>target){
                  do {right--;} while(left<right && num[right]==num[right+1]);
              }
              else if (value<target){
                  do {left++;} while (left<right && num[left]==num[left-1]);
              }
              
            }
        }
        return result;
        
    }
}


public class Solution {
    public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        
        int min=Integer.MAX_VALUE;
        int result=0;
        
        for (int i=0; i<num.length; i++){
            if (i>0&&num[i]==num[i-1]) continue;
            
            int start=i+1; 
            int end=num.length-1;
            
            while(start<end){
                int sum=num[i]+num[start]+num[end];
                
                if (sum>target){
                    int diff=sum-target;
                    if (diff<min){
                        min=diff;
                        result=sum;
                    }
                    do {end--;} while(start<end && num[end]==num[end+1]);
                }
                else if (sum<target){
                    int diff=target-sum;
                    if (diff<min){
                        min=diff;
                        result=sum;
                    }
                    do {start++;} while(start<end&& num[start]==num[start-1]);
                }
                else{
                    min=0;
                    result=sum;
                    break;
                }
            }
        }
        return result;
    }
}