Tuesday, July 22, 2014

2Sum && 3Sum && 3Sum Closest && 4Sum

3Sum Closest
public class Solution {
    //Time: O(n^2)  Space: O(1)
    public int threeSumClosest(int[] num, int target) {
        if (num == null || num.length < 3) {
            return -1;
        }
        
        Arrays.sort(num);
        int closest = Integer.MAX_VALUE / 2;
        for (int i = 0; i < num.length; i++) {
            int left = i + 1;
            int right = num.length - 1;
            while (left < right) {
                int cur = num[i] + num[left] + num[right];
                if (Math.abs(cur - target) < Math.abs(closest - target)) {
                    closest = cur;
                    if (closest == target) {
                        return target;
                    }
                }
                if (cur < target) {
                    left++;
                } else if (cur > target) {
                    right--;
                }
            }
        }
        return closest;
    }
}

No comments:

Post a Comment