3Sum Closest

Intuition

After sorting, fixing the first element lets the two remaining pointers respond to feedback: when the current sum is below the target we shift the left pointer up to raise it, and when it is above we shift the right pointer down to lower it. Along the way we compare the absolute gap between each sum and the target, remembering whichever total sits closest. If a sum ever equals the target exactly, no closer value can exist, so we can stop immediately.

Algorithm walkthrough

1. 1Sort the array so pointer moves change the sum in a predictable direction.
2. 2Initialize the best answer with the first three elements' sum.
3. 3For each fixed index i, place left just after i and right at the end.
4. 4Update the best answer whenever the current three-way sum is nearer to the target than the stored one.
5. 5Move left up if the sum is below target, right down if above, and return early on an exact match.

Implementation

from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        closest = nums[0] + nums[1] + nums[2]
        for i in range(n - 2):
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if abs(total - target) < abs(closest - target):
                    closest = total
                if total < target:
                    left += 1
                elif total > target:
                    right -= 1
                else:
                    return total
        return closest