【刷题记录】16. 最接近的三数之和

一、题目描述

来源：力扣（LeetCode）

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1

输出：2

解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1

输出：0

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

二、思路分析

排序 + 双指针

这道题目其实是上道题 【刷题记录】15.三数之和 的一个变形，上个题目目的是找到 sum == 0 而这道题是 找到 sum == target 或者最接近target的，在上道题目的基础上

• 根据 sum = L + nums[i] + R 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 res
• 判断 sum 与 target 的大小关系时，因为数组有序，如果 sum > target 则 R--，如果 sum < target 则 L++，如果 sum == target 则说明距离为 0 直接返回结果

三、代码实现

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        //初始化一个res
        int res = nums[0] + nums[1] + nums[2];
for (int i =0; i < nums.length; i++) {
            //去重
if (i > 0 && nums[i] == nums[i -1]) continue;
            int R = i +1, L = nums.length -1;
while (R < L) {
                int sum = nums[R] + nums[L] + nums[i];
if (Math.abs(target - sum) < Math.abs(target - res))
                    res = sum;
if (sum > target)
                    L--;
elseif (sum < target)
                    R++;
else                    return res;
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：

空间复杂度：

运行结果

总结

这道题其实就是上个题目的一个变形，只要理解了上个题目的思想，这个题目就比较简单了。