16. 最接近的三数之和

2021-03-12

LeetCode

双指针

3 分钟读完 (大约 506 个字) 0次访问

leetcode 16. 最接近的三数之和

题目：16. 最接近的三数之和

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

示例:

输入: nums = [-1,2,1,-4], target = 1
输出: 2
解释: 与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

提示:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

方法：排序 + 双指针

思路：排序 + 双指针，先对数组进行从小到大排序，然后从大到小遍历出第一个整数a，对于剩下的两个整数 b和c，希望它们的和最接近 target-a。假设数组的长度为 n，我们先枚举 a，它在数组中的位置为 i，借助双指针（对撞指针）我们在位置[0,i-1]的范围内枚举 b和 c，初始时令b为i-1位置上的值，c为0位置上的值，如果a+b+c < target，则将c往右移一位，指向1位置的值；如果a+b+c > target，则将b往左移一位，指向i-2位置的值；如果a+b+c == target，则直接返回target，结束方法。

运行数据：执行用时：6 ms，内存消耗：38.2MB

// LeetCode指定调用方法
public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int bestSum = nums[0] + nums[1] + nums[2];
    for (int i = nums.length - 1; i >= 0; i--) {
        int l = 0;
        int r = i - 1;
        while (l < r) {
            int sum = nums[i] + nums[r] + nums[l];
            if (sum > target) {
                if (Math.abs(sum - target) < Math.abs(bestSum - target)) {
                    bestSum = sum;
                }
                r--;
            } else if (sum < target){
                if (Math.abs(sum - target) < Math.abs(bestSum - target)) {
                    bestSum = sum;
                }
                l++;
            } else {
                return target;
            }
        }
    }
    return bestSum;
}