2014年5月12日星期一

Loop Approach Solution - 3Sum Closest

The idea is same as 3Sum, but add a distance check and update the result each time/approach. Watch how the loop work. This one doesn't case duplicates anyway better to have.

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num == null || num.length < 3){
            return Integer.MIN_VALUE;
        }
        Arrays.sort(num);
        int i = 0;
        int result = num[0] + num[1] + num[2];
        int distance = Integer.MAX_VALUE;
        while(i < num.length - 2){
            int curTarget = target - num[i];
            int start = i + 1;
            int end = num.length - 1;
            while(start < end){
                if(Math.abs(num[start] + num[end] - curTarget) < distance){
                    distance = Math.abs(num[start] + num[end] - curTarget);
                    result = num[start] + num[end] + num[i];
                }
                if(num[start] + num[end] < curTarget){
                    start++;
                }else if(num[start] + num[end] > curTarget){
                    end--;
                } else{
                    return target;
                }
            }
            i++;
        }
        return result;
    }
}

没有评论: