16. 3Sum Closest

//O(n2) time and O(1) solution
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        //Sanity Check
        if(nums==null || nums.length<3) return 0;
        Arrays.sort(nums);
        int sum = nums[0] + nums[1] + nums[2]; 
        for(int i=0;i<nums.length-2;i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            int low = i+1, high = nums.length-1;
            while(low<high){
                int cursum = nums[low] + nums[high] + nums[i];
                if(cursum==target){
                    return cursum;
                }
                else if(cursum<target){
                    if(Math.abs(cursum-target)<Math.abs(sum-target))
                        sum = cursum;
                    low++;
                }
                else{
                    if(Math.abs(cursum-target)<Math.abs(sum-target))
                        sum = cursum;
                    high--;
                }
            }
        }
        return sum;
    }
}