16.最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

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

示例 2：

1
2
输入：nums = [0,0,0], target = 1
输出：0

Solution：

上一道题要判重复，这道题不用，所以简单一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 对数组进行排序
        Arrays.sort(nums);
        // n是数组长度
        int n = nums.length;
        // res用于存储最接近目标值的三数之和，初始化为0
        int res = 0;
        // near用于记录当前找到的最接近目标值的差的绝对值，初始化为一个大数（这里是10^9）
        int near = (int) 1e9;

        // 外层循环，枚举第一个数
        for (int i = 0; i < n; ++i) {
            // 双指针，j指向i之后的元素，k指向数组最后一个元素
            for (int j = i + 1, k = n - 1; j < k; ) {
                // 计算当前三个数的和
                int sum = nums[i] + nums[j] + nums[k];
                // 如果当前和与目标值的差的绝对值小于已记录的最小差的绝对值
                if (near > Math.abs(target - sum)) {
                    // 更新最小差的绝对值和最接近目标值的三数之和
                    near = Math.abs(target - sum);
                    res = sum;
                }
                // 根据sum与target的比较，移动双指针以寻找更接近目标值的组合
                if (sum > target) {
                    // 如果和大于目标值，为了减小和，将k左移
                    --k;
                } else if (sum < target) {
                    // 如果和小于目标值，为了增大和，将j右移
                    ++j;
                } else {
                    // 如果和等于目标值，直接返回target，这是最接近的情况
                    return target;
                }
            }
        }
        // 返回找到的最接近目标值的三数之和
        return res;
    }
}