原题地址：. - 力扣（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 解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。提示：
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104
解题思路
- 排序：首先对数组进行排序，以便可以使用双指针法来寻找三个数的和。
- 遍历：使用一个循环固定第一个数
nums[i]，然后使用双指针slow和fast来查找另外两个数，使得三数之和最接近给定的目标值。- 计算差值：每次计算三数之和，并更新与目标值的最小差值及最近的和。如果找到完全匹配的和，直接返回。
- 移动指针：根据三数之和与目标值的大小关系，移动指针：
- 如果和小于目标值，移动左指针以增加和。
- 如果和大于目标值，移动右指针以减少和
代码实现
class Solution {
public int threeSumClosest(int[] nums, int target) {
// 输入有效性检查
if (nums == null || nums.length < 3) {
return 0; // 由于没有足够的数，返回 0
}
int minDifference = Integer.MAX_VALUE; // 最小差值初始化为最大值
int closestSum = 0; // 最近和初始化为 0
// 排序数组
Arrays.sort(nums);
// 遍历数组，固定第一个数
for (int i = 0; i < nums.length - 2; i++) {
int slow = i + 1; // 左指针
int fast = nums.length - 1; // 右指针
// 使用双指针查找最接近的三数之和
while (slow < fast) {
int sum = nums[i] + nums[slow] + nums[fast]; // 计算三数之和
// 更新最小差值和最近和
if (Math.abs(sum - target) < minDifference) {
minDifference = Math.abs(sum - target);
closestSum = sum;
}
// 根据三数之和与目标值的比较移动指针
if (sum < target) {
slow++; // 和小于目标，移动左指针
} else if (sum > target) {
fast--; // 和大于目标，移动右指针
} else {
return sum; // 找到完全匹配，直接返回
}
}
}
return closestSum; // 返回最接近的和
}
}
复杂度分析
标签：target,nums,int,三数,sum,LeetCode16,接近,指针 From： https://blog.csdn.net/qq_36070104/article/details/143339116
- 时间复杂度：O(n²)，外层循环遍历每个元素，内层双指针查找组合。数组排序的时间复杂度为 O(n log n)，整体复杂度为 O(n²)。
- 空间复杂度：O(1)，只使用了常量级别的额外空间（不考虑结果值的空间）。