Leetcode 16 3Sum Closest

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Input: nums = [0,0,0], target = 1
Output: 0

• 3Sum Closest is a follow-up question for two sum.

For 3Sum Closest, we are going to find the closest sum to the target. The closest sum could be the target itself or a number close to the target.

First, we can sort the array into ascending order. Second, we declare an integer variable called closetSum. That’s the final value we are going to return. Then we can iterate all the numbers in the array. Whenever visiting a number, we should find two numbers in the rest of array which adds the number closet to target. Once iteration finished, we get the result.

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        three_sum_closest = sys.maxsize
        
        nums = sorted(nums)
                
        for i, num in enumerate(nums):        
            l = i + 1
            r = len(nums) - 1
            #ignore the duplicate numbers
            if i > 0 and nums[i] == nums[i-1]:
                continue            
            while l < r:       
                local_sum = nums[i] + nums[l] + nums[r]
                if abs(local_sum - target)  < abs(three_sum_closest - target):
                    three_sum_closest = local_sum
                
                if local_sum <= target:
                    l += 1
                else:
                    r -= 1
        
        return three_sum_closest