Leetcode之16-最接近的三数之和(3Sum Closes

前言

个人网站

公众号: 北京程序猿, 网站 : https://yaml.vip

算法题

题干

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1。与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法

本题同样比较简单, 第一步就是排序, 排序后采用双指针才更方便向中间靠拢。与三数之和思路一样, 唯一的区别是本道算法题需要两个变量用来存储差与和。

Java代码

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int minDiff = Integer.MAX_VALUE, data = 0;
    final int LEN = nums.length;
    for (int i = 0; i < LEN - 2; i++) {
        int left = i + 1, right = LEN - 1;
        while(left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == target) {
                return target;
            }
            if (Math.abs(sum - target) < minDiff) {
                minDiff = Math.abs(sum - target);
                data = sum;
            }
            if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
    }
    return data;
}

代码解析

1. 第3行代码中变量minDiff表示最小差值, data表示三数之和。
2. 第5行代码for循环中i<LEN-2表示外层循环到倒数第三个数即可, 毕竟题目找三数之和。
3. 第7行代码while循环表示双指针left和right向中间靠拢。
4. 剩余代码表示如果和sum恰好等于三数之和即直接返回, 然后判断差值, 最后再确定是向右向左靠拢。

本文著作权归作者所有。

商业转载请联系作者获得授权，非商业转载请于文首标明作者姓名，保持文章完整性，并附上出处和文章链接！未按规范转载者，作者保留追究相应责任的权利！

作者：北京程序猿

链接：最接近的三数之和