【leetcode】16. 最接近的三数之和

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解答

这道题和三数之和类似，没看过三数之和的可以看下三数之和，两道题的解决思路几乎一样，只不过这道题需要不停着记录三个数的和与 target 之间的差。我就直接给出代码了，如果你看懂了三数之和，那么这道题的代码一下就能看懂了。代码如下：

    public static int threeSumClose(int[] nums, int target) {
        //存他们之间的差
        int result = Math.abs(nums[0] + nums[1] + nums[2] - target);
        int sum = nums[0] + nums[1] + nums[2];
        //排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            } else {
                int j = i + 1;
                int k = nums.length - 1;
                int temp = target - nums[i];

                while (j < k) {
                    int t = nums[j] + nums[k];
                    if (t < temp) {
                        if (result > temp - t) {
                            result = temp - t;
                            sum = t + nums[i];
                        }
                        j++;
                    } else if (t > temp) {
                        if (Math.abs(result) > t - temp) {
                            result = t - temp;
                            sum = t + nums[i];
                        }
                        k--;
                    } else {
                        return nums[i] + t;
                    }
                }
            }

        }
        return sum;
    }

往期