Wednesday, October 17, 2012

[LeetCode] 3Sum closest

Question:

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.

解题思路:
              与3Sum一样

Java code:


public int threeSumClosest(int[] num, int target) {
        Arrays.sort(num);
        int closestNum = Integer.MAX_VALUE;
        
        for(int i = 0; i < num.length - 2; i++){
            int j = i+1;
            int t = num.length - 1;
            
            while(j < t){
            int total = num[i] + num[j] + num[t] - target;
            
            if(total == 0){
                return target;
            }
            
            closestNum = Math.abs(total) < Math.abs(closestNum) ? total : closestNum;
            
            if(total > 0){
                t--;
                
                while(j < t && num[t] == num[t+1]) t--;
            }else{
                j++;
                
                while(j < t && num[j] == num[j-1]) j++;
            }
          }
          
          while(i < num.length - 2 && num[i] == num[i+1]) i++;
        }
        
        
        return closestNum + target;
        
    }

No comments:

Post a Comment