Daily LeetCode Challenge (Day 14) #16. 3Sum Closes

Photo by Dan Cristian Pădureț on Unsplash

Difficulty | Medium

Description

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

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

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Approach

Use a two-pointer approach to find the three integers in nums that add up to the closest sum to target.
The algorithm to first sort the input array in ascending order.
Then initialise the closest sum to the sum of the first three elements in the sorted array.
Then iterate through each element of the array, treating it as the first element of a possible three-sum combination.
For each first element, use two pointers, left and right, to search for the two other elements that sum to the closest possible value to target.
The pointers start at the first element after the first element and at the last element of the array, respectively.
The pointers move towards each other until they meet. For each combination of nums[i], nums[left], and nums[right], the algorithm computes the sum and checks if it is closer to target than the current closest sum.
If it is, the closest sum is updated. Finally, the algorithm returns the closest sum found.

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
  // sort the array in ascending order
  nums.sort((a, b) => a - b); 
  // initialize closest sum to the sum of the first three elements
  
  let closestSum = nums[0] + nums[1] + nums[2]; 

  for (let i = 0; i < nums.length - 2; i++) {
    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(closestSum - target)) {
        closestSum = sum;
      }

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

  return closestSum
};