题目

给你一个长度为 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

提示：

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

题解

public int threeSumClosest(int[] nums, int target) {
    // 排序數組
    Arrays.sort(nums);
    // 最接近target的值
    int closestTarget = nums[0] + nums[1] + nums[2];
    // 类似快排的方式找到三个和为0的数字
    for (int i = 0, length = nums.length; i < length; i++) {
        int j = i + 1;
        int k = length - 1;
        while (j < k && k > i) {
            int iv = nums[i], jv = nums[j], kv = nums[k];
            int value = iv + jv + kv;
            if (value < target) {
                j++;
            } else if (value > target) {
                k--;
            } else {
                return target;
            }

            if (Math.abs(target - value) < Math.abs(target - closestTarget)) {
                closestTarget = value;
            }
        }
    }

    return closestTarget;
}