[Sum][Two Pointers] 3Sum Closest

1. Example

s = [-1,2,1,-4] and target =1
A closest sum is  2
(-1+2+1 = 2 )


2. Implementation
Q1: 3Sum check exactly equal, how about closest?
A1: Equal means diff = 0, closest means diff is min. So we calculate the difference and choose the minimum
int min = (num[0]+num[1]+num[2]) - target ;

int diff = twoSum(nums, i-1, target - num[i]);

if ( Math.abs(diff) < Math.abs(min) )

if ( nums[l] + nums[r] == target ) { // Exactly one solution // NOTE: return diff return 0; }
return min;
return target + diff;

// time:O(n^3), Space:O(1)

public int threeSumClosest(int[] nums, int target)
{
    

     // validate the input
     if ( nums == null || nums.length < 3 )
     {    
          // sum may be zero, so we return min
          //return 0;
          return Integer.MIN_VALUE;
     }




     Arrays.sort(nums);






     int min = (num[0]+num[1]+num[2]) - target ;
     // NOTE :  i-1, so starting point 2
     for(int i = nums.length -1; i > 1 ;i--)
     {       
           // Exactly one solution, no need to avoid duplicate   
           //if ( i == num.length -1 || num[i] != num[i+1])
           //{
                    //int threesum = num[i] + twoSum(nums, i-1, target- nums[i]);
                    //int diff =  threesum - target  ;
                    
                    int diff = twoSum(nums, i-1, target - num[i]);
                    if (   Math.abs(diff) < Math.abs(min)  )
                    {
                        min = diff;
                    } 
           //}
     }
     



     // NOTE : even for two sum diff = num[l]+num[r] - target', where target' = target - num[i], so diff = num[l] + num[r] + num[i] - target
     return target + diff;



}


private int twoSum (int[] nums, int end, int target)
{





     if (  nums== null | nums.length < 2)
     {
           return Integer.MIN_VALUE;
     }

     


     int min =  (num[0] + num[end]) - target ;
     int l = 0; 
     int r = end;
     while(   l < r  )
     {
              int diff = (num[l]+num[r]) - target  ;
              if ( nums[l] + nums[r] == target )
              {
                    // Exactly one solution
                    // NOTE: return diff
                    return 0;
              }
              else if (  nums[l] + nums[r] > target )
              {
                    r--;
              }
              else 
              {
                    l++;
              }
              if ( Math.abs(diff)  < Math.abs(min)  )
              {
                    min = diff;
              }
     }


     return min;
     //return target + diff;



}

3. Similar ones
3Sum
3Sum Smaller