题目描述 16. 最接近的三数之和

给定一个包括 n 个整数的数组nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例1
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

思路

参考之前的文章三数之和，我们可以知道，本题如果想要采用双指针的思路，那么也要首先对数组进行排序。
其实本题的思路和三数之和极其相似，首先我们对数组进行排序，然后遍历数组，下标index从，每次遍历中，我们定义双指针left = index + 1和right = nums.length - 1，我们可以得到一个三数和

sum = nums[index] + nums[left] + nums[right]

对于这个sum我们比较它和target相差多少，每次遍历都比较一次，如果小于原先记录的最小值，则更新这个最小值，遍历结束后我们既可以找到最小值所对应的sum值。
JavaScript代码实现如下

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
    if (nums.length === 3) return nums[0] + nums[1] + nums[2]
    let res
    let min = Infinity
    // 首先进行数组排序
    nums.sort((a, b) => {
        return a - b
    })
    for (let i = 0; i < nums.length - 2; i++) {
        let base = nums[i]
        let left = i + 1
        let right = nums.length - 1
        while (left < right) {
            let sum = base + nums[left] + nums[right]
            let diff = Math.abs(sum - target)
            if (diff < min) {
                min = diff
                res = sum
            }
            if (sum < target) {
                left++
            } else if (sum > target) {
                right--
            } else if (sum === target) {
                return res
            }
        }
    }
    return res
}
// test
console.log(threeSumClosest([-1, 2, 1, -4], 1))

补充Java代码实现

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
    }

    public static int threeSumClosest(int[] nums, int target) {
        if (nums.length == 3) return nums[0] + nums[1] + nums[2];
        int res = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        // 对数组进行排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int base = nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = base + nums[left] + nums[right];
                int diff = Math.abs(sum - target);
                if (diff < min) {
                    min = diff;
                    res = sum;
                }
                // 若sum < target，说明三数和太小，需要向右移动左指针
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {   // 相当则直接返回当前的res，即sum
                    return res;
                }
            }
        }
        return res;
    }
}