3Sum Closest

Problem Statement

Given an array nums and a target, find three integers whose sum is closest to the target. Return that sum (exactly one answer is assumed).

Example

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

Two Pointer Approach

Sort the array first. Fix each index i as the smallest of the triplet, then run two pointers (left = i+1, right = n-1) inward. Track the closest sum seen; move left up if the sum is below target, or right down if it is above.

Complexity

• Time: O(n^2)
• Space: O(1) extra (ignoring the sort)

Solution Code

Python

def threeSumClosest(nums, target):
    nums.sort()
    best = nums[0] + nums[1] + nums[2]
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if abs(s - target) < abs(best - target):
                best = s
            if s < target:
                left += 1
            elif s > target:
                right -= 1
            else:
                return s
    return best

Java

int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int best = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int s = nums[i] + nums[left] + nums[right];
            if (Math.abs(s - target) < Math.abs(best - target)) best = s;
            if (s < target) left++;
            else if (s > target) right--;
            else return s;
        }
    }
    return best;
}

C++

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int best = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < (int)nums.size() - 2; i++) {
        int left = i + 1, right = (int)nums.size() - 1;
        while (left < right) {
            int s = nums[i] + nums[left] + nums[right];
            if (abs(s - target) < abs(best - target)) best = s;
            if (s < target) left++;
            else if (s > target) right--;
            else return s;
        }
    }
    return best;
}

Key Takeaways

• Sorting is what unlocks the two pointer move decisions.
• Track the best difference with abs(s - target).
• Return early if an exact match (difference 0) is found.