3.5 3 Sum Closest

3.5.1 Problem Metadata

3.5.2 Description

Given an integer array nums and an integer target, return the sum of three integers in nums such that the sum is closest to target. Each input has exactly one solution.

Note: This problem is part of the N Sum Family pattern. See the comparison table in the chapter introduction for a comprehensive comparison of all Two Sum, Three Sum, and Four Sum variants.

3.5.3 Examples

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The triplet [-1,2,1] sums to 2, which is closest to target.

3.5.4 Constraints

  • 3 <= nums.length <= 1000
  • -10^3 <= nums[i], target <= 10^3

3.5.5 Solution - Sort + Two Pointers

3.5.5.1 Walkthrough

  1. Sort the array so pointer sweeps over the interior become possible.
  2. Iterate i from 0 to n - 3. Treat nums[i] as the first term, then run left/right pointers to scan the remainder.
  3. Track the closest sum seen so far and update it whenever a tighter candidate appears.

3.5.5.2 Analysis

  • Time Complexity: O(n�)
  • Space Complexity: O(1) auxiliary

3.5.5.3 Implementation Steps

  1. Sort nums.
  2. Initialize closest = nums[0] + nums[1] + nums[2].
  3. For each i in [0, n - 3]:
    1. Set left = i + 1, right = n - 1.
    2. While left < right:
      • sum = nums[i] + nums[left] + nums[right].
      • If |target - sum| < |target - closest|, update closest.
      • Move left or right inward depending on whether sum is less or greater than target.
  4. Return closest.

3.5.5.4 Code - Java

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int closest = nums[0] + nums[1] + nums[2];

    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (Math.abs(target - sum) < Math.abs(target - closest)) {
                closest = sum;
            }

            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return sum;
            }
        }
    }

    return closest;
}