3Sum Closest

medium array two pointers sorting

Problem

Given an integer array nums and an integer target, find three integers in nums whose sum is closest to target and return their sum.

Inputnums = [-1, 2, 1, -4], target = 1

Output2

The triplet (-1, 2, 1) sums to 2, closest to target 1.

nums (comma-separated)

target

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

function threeSumClosest(nums, target) {
  nums.sort((a, b) => a - b);
  let best = nums[0] + nums[1] + nums[2];
  for (let i = 0; i < nums.length - 2; i++) {
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      const s = nums[i] + nums[l] + nums[r];
      if (Math.abs(s - target) < Math.abs(best - target)) best = s;
      if (s < target) l++;
      else if (s > target) r--;
      else return s;
    }
  }
  return best;
}

class Solution {
    public 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 l = i + 1, r = nums.length - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (Math.abs(s - target) < Math.abs(best - target)) best = s;
                if (s < target) l++;
                else if (s > target) r--;
                else return s;
            }
        }
        return best;
    }
}

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 l = i + 1, r = nums.size() - 1;
        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];
            if (abs(s - target) < abs(best - target)) best = s;
            if (s < target) l++;
            else if (s > target) r--;
            else return s;
        }
    }
    return best;
}

Explanation

We need three numbers whose sum is as close as possible to a target. After sorting the array, we can fix one number and use a two-pointer sweep for the other two, which is much faster than trying every triple.

For each fixed index i, a left pointer l starts just after it and a right pointer r starts at the end. We compute s = nums[i] + nums[l] + nums[r] and remember it in best whenever it is nearer to the target than what we had.

The sorted order tells us how to move: if s < target the sum is too small so we move l right to grow it; if s > target we move r left to shrink it. If s equals the target, that is the closest possible and we return immediately.

Example: nums = [-4, -1, 1, 2] (sorted), target 1. Fixing -1 with l=1, r=2 gives -1+1+2 = 2, which is distance 1 from the target and becomes the best.

Because each fixed i sweeps the rest in one linear pass, the whole thing runs in about n-squared time and never needs to look at the same pair twice.

Time: O(n²) Space: O(1)