题目描述

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

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

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

https://leetcode-cn.com/problems/3sum-closest/

解法1

这道题目与三数之和非常相似, 不同之处在于本题要求解的是最接近目标值的三数之和而不要求三数之和为0. 另一个不同点是, 题目给定的输入能保证只存在唯一答案.

我们还是使用“三数之和”解法1的做法, 首先将数组nums排序,以降低内层循环的时间复杂度. 变量i依次访问数组nums的每个元素, 作为外层循环. 内层循环中, 我们用j, k指针分别指向i之后数组的两端. 我们将nums[i]+nums[j]+nums[k]与target之差的绝对值记为diff, diff的初值为Integer.MAX_VALUE. 如果nums[i]+nums[j]+nums[k]与target之差的绝对值小于diff, 则更新diff. 题目要求nums[i]+nums[j]+nums[k]的和, 那么我们除了记录diff之外, 还应该记录与diff对应的三个数之和, 我们计作threeSum.

现在我们分析下如何维护变量j与k. 如果三个数之和小于target, 那么说明我们要找更大的数才能使三数之和更接近target, 所以j自增1. 如果三数之和大于target, 说明我们从右边选的数太大了, 应该k自减1. 如果三数之和与target相等, 那么三数之和与target的差距是0, 这是最接近target的情况了. 注意, 如果遇到这种情况, 我们需要将j自增1, k自减1, 否则将陷入死循环(代码中标记的部分). 我在第一次提交就犯了这个错误, 没有修改j, k变量导致死循环.

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int diff = Integer.MAX_VALUE;
        int threeSum = 0;

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int sum = num + nums[j] + nums[k];

                if (Math.abs(sum - target) < diff) {
                    diff = Math.abs(sum - target);
                    threeSum = sum;
                }


                if (sum < target)
                    j++;
                else if (sum > target)
                    k--;
                else {
                    j++;
                    k--;
                }
            }
        }

        return threeSum;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *