3Sum Closest

Problem

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

Constraints:

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10⁴ <= target <= 10⁴

Solution

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

    for (let i = 0; i < nums.length - 2; i++) {
        // skip duplicate starting values
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }

        // modified sorted two sum solution
        const sum = target - nums[i];
        let lo = i + 1;
        let hi = nums.length - 1;

        while (lo < hi) {
            const val = nums[lo] + nums[hi];
            if (val > sum) {
                hi--;
            } else if (val < sum) {
                lo++;
            } else {
                return target;
            }
            if (Math.abs(res - target) > Math.abs(val - sum)) {
                res = val + nums[i];
            }
        }
    }
    return res;
};

The solution is similar to the 3Sum problem. The only difference is we keep track of the triplet with sum closest to target instead of all triplets that add up to 0.

Problem​

Solution​

Problem

Solution