16. 3Sum Closest {Medium}

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

rarara's solution:

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # IMPORTANT! First, sort the elements
        nums.sort()
        count = len(nums)
        closest_sum = 0
        min_diff = 0xFFFFFFFF

        # Iterate through each of the elements
        for i, n in enumerate(nums):
            left = i + 1
            right = count - 1

            # Use 2 pointers
            # Iterate through the elements to the right of the current element
            while left < right:
                sum = n + nums[left] + nums[right]

                # If sum == target, we are done
                if sum == target:
                    return sum

                elif sum > target:

                    # Find the diff
                    # Store the sum if diff is lesser than current minimum diff
                    diff = sum - target
                    if diff < min_diff:
                        closest_sum = sum
                        min_diff = diff

                    # If sum > target, move right pointer to the left
                    right -= 1

                # If sum < target, move left pointer to the right
                else:

                    # Find the diff
                    # Store the sum if diff is lesser than current minimum diff
                    diff = target - sum
                    if diff < min_diff:
                        closest_sum = sum
                        min_diff = diff

                    # If sum > target, move right pointer to the left
                    left += 1

        return closest_sum