LeetCode-最接近的三数之和（016）

2025/3/10 19:20:47 来源：https://blog.csdn.net/fulai00/article/details/144883246 浏览: 次关键词：LeetCode-最接近的三数之和（016）

一.题目描述

给你一个长度为 `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
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

三.提示：

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

四.解法:

方法一：排序 + 双指针

我们将数组排序，然后遍历数组，对于每个元素 nums[i]，我们使用指针 j 和 k 分别指向 i+1 和 n−1，计算三数之和，如果三数之和等于 target，则直接返回 target，否则根据与 target 的差值更新答案。如果三数之和大于 target，则将 k 向左移动一位，否则将 j 向右移动一位。

时间复杂度 O(n2)，空间复杂度 O(log⁡n)。其中 n 为数组长度。

五.代码

Java代码

class Solution {public int threeSumClosest(int[] nums, int target) {// 首先对数组进行排序Arrays.sort(nums);// 初始化答案为一个很大的数int ans = 1 << 30;// 获取数组的长度int n = nums.length;// 遍历数组，寻找最接近目标的三元组for (int i = 0; i < n; ++i) {// 使用双指针法int j = i + 1, k = n - 1;while (j < k) {// 计算当前三元组的和int t = nums[i] + nums[j] + nums[k];// 如果和等于目标值，直接返回if (t == target) {return t;}// 更新答案，如果当前和更接近目标if (Math.abs(t - target) < Math.abs(ans - target)) {ans = t;}// 根据和与目标的大小关系调整指针if (t > target) {--k; // 如果和大于目标，移动右指针以减小和} else {++j; // 如果和小于目标，移动左指针以增加和}}}// 返回最接近目标的三元组的和return ans;}
}注释说明·排序：首先对数组进行排序，以便使用双指针法。·初始化答案：ans 初始化为一个很大的数，用于存储最接近目标的三元组的和。·遍历数组：外层循环遍历数组，寻找可能的三元组。·双指针法：使用两个指针 j 和 k，分别从当前元素的下一个位置和数组末尾开始。·计算和：计算当前三元组的和 t。·直接返回：如果 t 等于目标值 target，直接返回 t。·更新答案：如果 t 更接近目标值 target，更新 ans。·调整指针：根据 t 和 target 的大小关系调整指针位置。·如果 t > target，移动右指针 k。·如果 t < target，移动左指针 j。·返回结果：返回最接近目标的三元组的和。