当前位置：网站首页>【刷题记录】16. 最接近的三数之和

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

2022-07-20 19:36:00 【InfoQ】

一、题目描述

来源：

力扣（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--;
 else if (sum < target)
 R++;
 else
 return res;
 }
 }
 return res;
 }
}