Medium

3Sum Closest

LAB

Return the sum of three integers in nums closest to target.

EXAMPLES

Example 1

Input
{
  "nums": [
    -1,
    2,
    1,
    -4
  ],
  "target": 1
}

Output
2

FUNCTION SHAPE

nums: intArraytarget: int→int

SOLUTION NOTE

A combination of the previous 3 Sum problems. We want the closest triplet sum to target (from below OR above).

The subtle difference is that we update res whenever the current triplet sum is closer to target than our best so far. We discard pairs with a sum further from the target than our current sum.

Reveal reference solution +

pythonREFERENCE

def threeSumClosest(self, nums: List[int], target: int) -> int:
    n = len(nums)
    nums.sort()
    res = inf

    for i in range(n):
        j = i + 1
        k = n - 1

        while j < k:
            if abs(nums[i] + nums[j] + nums[k] - target) < abs(res - target):
                res = nums[i] + nums[j] + nums[k]

            if nums[j] + nums[k] < target - nums[i]:
                j += 1
            else:
                k -= 1

    return res

TimeO(n²)

SpaceO(1)

Open on LeetCode ↗