LeetCode. 16. 3Sum Closest

[Link] https://leetcode.com/problems/3sum-closest/

Given an integer array nums and an integer target, return the sum of three distinct elements that is closest to target. If multiple sums are equally close, any of them may be returned.

Sort the array in ascending order, then fix each element in turn as the first of the three. Search for the other two with pointers starting at opposite ends of the remaining range. If their sum is below the target, move the left pointer right to increase it; if it is above, move the right pointer left to decrease it. At each step, keep whichever of the current sum and the best sum so far is closer to the target. Return immediately on an exact match, since no closer result is possible.

Skipping duplicate fixed values and pointer values avoids repeating equivalent cases without changing the possible closest result; it is an optimization, not a correctness requirement.

Sorting takes O(N log N), and the two-pointer scan takes O(N) for each fixed element, for O(N²) total time. The search uses O(1) extra space apart from sorting. JavaScript’s Array.prototype.sort may use engine-dependent auxiliary memory, so the total auxiliary-space bound including the sort depends on the runtime implementation rather than being universally O(1).

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function threeSumClosest(nums, target) {
  nums.sort((a, b) => a - b);

  let closest = nums[0] + nums[1] + nums[2];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = nums.length - 1;

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

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

      if (sum < target) {
        const leftValue = nums[left];
        while (left < right && nums[left] === leftValue) left++;
      } else {
        const rightValue = nums[right];
        while (left < right && nums[right] === rightValue) right--;
      }
    }
  }

  return closest;
}