Sunday, January 11, 2015

16. 3Sum Closest Leetcode Java

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:
Two pointers.
Similar to 3Sum
Now we need to check if the sum is closer target and update the res correspondingly. Also we can skip those element with same values if it has been processed.
Time complexity: O(n^2)


  public int threeSumClosest(int[] num, int target) {  
    if(num==null || num.length<3) return 0;  
    Arrays.sort(num);  
    int res=num[0]+num[1]+num[2];  
    for(int i=0;i<num.length-2;i++){  
      int l=i+1;  
      int r=num.length-1;  
      while(l<r){  
        int sum=num[i]+num[l]+num[r];  
        if(sum==target) return sum;  
        else if(sum<target) l++;  
        else r--;  
        if(Math.abs(sum-target)<Math.abs(res-target)) res=sum;  
      }  
      while(i<num.length-2 && num[i+1]==num[i]) i++;  
    }  
    return res;  
   }  

No comments:

Post a Comment