問題描述

給定一個包括 n 個整數的數組 nums 和一個目標值 target，請你找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組內沒有重複的整數。

示例

示例 1: 輸入: nums = [-1,2,1,-4], target = 1 輸出: 2 解釋: 與 target 最接近的和是 2。（-1 + 2 + 1 = 2）

示例 2: 輸入: nums = [0,0,0], target = 1 輸出: 0 解釋: 與 target 最接近的和是 0。（0 + 0 + 0 = 0）

解法一

解題思路: 我們可以使用雙指針的方法來解決這個問題。首先對數組進行排序，然後遍歷數組，對於每個元素，使用兩個指針分別指向其後的第一個元素和最後一個元素，通過移動這兩個指針來尋找和最接近 target 的三個數。

/*
 * @lc app=leetcode.cn id=16 lang=javascript
 *
 * [16] 3Sum Closest
 */

// @lc code=start
function threeSumClosest(nums, target) {
    nums.sort((a, b) => a - b);
    let closestSum = nums[0] + nums[1] + nums[2];
    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right];
            if (Math.abs(target - sum) < Math.abs(target - closestSum)) {
                closestSum = sum;
            }
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            } else {
                return sum;
            }
        }
    }
    return closestSum;
}
// @lc code=end