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.

    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).

Tags

• Array

Thought

The solution is similar to the 3Sum and we check the difference between the target and the sum of the three item during the loop.

Code

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        ans = None
        minDiff = float('inf')
        nums.sort()
        for i in xrange(len(nums) - 2):
            if i == 0 or nums[i] > nums[i - 1]:
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    diff = target - (nums[left] + nums[right] + nums[i])
                    if abs(diff) < minDiff:
                        ans = nums[left] + nums[right] + nums[i]
                        minDiff = abs(diff)
                    if diff == 0:
                        return ans
                    elif diff > 0:
                        left += 1
                    else:
                        right -= 1
        return ans