最接近的三数之和

[编程题]最接近的三数之和

热度指数：1486 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组 nums 和一个目标值 target ，请问从 nums 中选出三个数，使其之和尽量接近目标数，即三数之和与目标数只差绝对值尽可能小。

返回满足题面要求的三数之和。

数据范围：数组长度满足 $3 \le n \le 300 \$ ，数组中的值满足 $|nums[i]| \le 1000 \$ ，目标值满足 $|target| \le 10^4 \$ ，可以保证只有一个结果。

示例1

输入

[-1,2,1,-4],1

输出

说明

最接近 1 的三数之和是 -1+2+1 = 2

示例2

输入

[0,0,0],1

输出

说明

 只有一种选择 0+0+0

示例3

输入

[0,1,0,0],0

输出

算法知识视频讲解

Java

菲尼克斯弗兰克

排序+双指针

public class Solution {
    public int ClosestSum (int[] nums, int target) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE, res = 0;
        for (int i = 0; i < nums.length-2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int start = i + 1, end = nums.length-1, sum = 0, dif = 0;
            while (start < end) {
                sum = nums[i] + nums[start] + nums[end];
                dif = Math.abs(sum-target);
                if (dif < min) {
                    min = dif;
                    res = sum;
                }
                if (sum > target) {
                    end--;
                    while (start < end && nums[end+1]== nums[end]) end--;
                } else if (sum < target) {
                    start++;
                    while (start < end && nums[start-1]== nums[start]) start++;
                } else return target;
            }
        }
        return res;
    }
}

发表于 2022-02-08 15:15:12 回复(0)