题目描述
给你一个长度为 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
-10^4 <= target <= 10^4
题目评估
知识点：数组、双指针、排序
官方难度：中等
分析
本体思虑和上一题（三数之和）类似，只不过是把和换成了最接近的一个数。
Java代码题解
class Solution {
public int threeSumClosest(int[] nums, int target) {
int res = nums[0] + nums[1] + nums[2];
// 从小到大排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 第一个数字去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 计算二指针和三指针
int j = i + 1;
int k = nums.length - 1;
// 双指针遍历
while (j < k) {
// 求和
int sum = nums[i] + nums[j] + nums[k];
// 等于目标直接返回
if (sum == target) {
return sum;
}
// 计算
if (Math.abs(sum - target) < Math.abs(res - target)) {
// 更换最接近的结果
res = sum;
}
if (sum > target) {
// 和大于目标值，和需要减小，左移三指针
do {
k--;
} while (j < k && nums[k] == nums[k + 1]);
} else {
// 和小于等于目标值，和需要增加，右移二指针
do {
j++;
} while (j < k && nums[j] == nums[j - 1]);
}
}
}
return res;
}
}
复杂度分析
时间复杂度：O(N^2)，其中 N 是数组 nums 的长度。我们首先需要O(NlogN) 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(N) 枚举 a，双指针 O(N) 枚举 b 和 c，故一共是 O(N^2)。
空间复杂度：O(logN)。排序需要使用 O(logN) 的空间。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，此时空间复杂度为 O(N)。