3Sum Closest

Problem: 3Sum Closest

The solution of this problem is quite similar to the original problem. We sort the array first. Then we start scanning each number. When we are dealing with each number, we use two pointers to find possible results, one starting from the head, the other starting from the end.

Code in Python:

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        ans, min = sum(nums[:3]), abs(sum(nums[:3])-target)
        nums = sorted(nums)
        n = len(nums)
        for i in xrange(n):
            j, k = i+1, n-1
            while j < k:
                tmp = nums[i]+nums[j]+nums[k]
                if tmp == target: return tmp
                if abs(tmp-target) < min: ans, min = tmp, abs(tmp-target)
                if tmp < target:
                    j += 1
                    while j<n and nums[j] == nums[j-1]: j += 1
                else:
                    k -= 1
                    while k>=0 and nums[k] == nums[k+1]: k -= 1
        return ans

Code in Java:

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int res = nums[0]+nums[1]+nums[2], dist = Math.abs(target-res);
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            int j = i+1, k = nums.length-1;
            while (j < k) {
                int sum = nums[i]+nums[j]+nums[k];
                if (Math.abs(sum-target) < dist) {
                    res = sum;
                    dist = Math.abs(sum-target);
                }
                if (nums[j]+nums[k] <= target-nums[i]) {
                    while (j+1 < nums.length && nums[j+1] == nums[j])
                        j++;
                    j++;
                } else {
                    while (k-1 >= 0 && nums[k-1] == nums[k])
                        k--;
                    k--;
                }
            }
        }
        return res;
    }
}