[LeetCode] 3Sum Closest

Problem:

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

Solution: O(n*n)

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