题目：
给你一个长度为
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
1. 思路
这道题与三数之和问题类似，只是要求返回与目标值最接近的三个数的和。可以使用双指针法来解决这个问题。首先对数组进行排序，然后固定一个数，再使用双指针来搜索其余两个数，计算它们的和与目标值的差的绝对值，不断更新最小的差值。最后返回最接近的三个数的和。
2. 解题方法
- 对数组进行排序，时间复杂度为 O(nlogn)。
- 初始化一个变量
closestSum用于记录最接近目标值的三个数的和。初始值设为数组的前三个数的和。 - 遍历数组，对每一个数固定为
nums[i]：- 初始化双指针
left = i + 1和right = n - 1，分别指向数组的左右两端。 - 在
left < right的条件下，计算当前三个数的和sum = nums[i] + nums[left] + nums[right]。 - 如果
sum与target的差的绝对值小于closestSum与target差的绝对值，则更新closestSum为sum。 - 如果
sum大于target，则将right左移一位；如果sum小于target，则将left右移一位；如果sum等于target，则直接返回sum。
- 初始化双指针
- 返回
closestSum。
3. 复杂度
- 时间复杂度：排序数组的时间复杂度为 O(nlogn)，固定一个数后使用双指针遍历数组的时间复杂度为 O(n^2)，总体时间复杂度为 O(n^2 + nlogn) = O(n^2)。
- 空间复杂度：O(1)。
4. Code
import java.util.Arrays;
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); // 对数组进行排序
int closestSum = nums[0] + nums[1] + nums[2]; // 初始化最接近目标值的三个数的和为数组的前三个数的和
for (int i = 0; i < nums.length; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right]; // 计算当前三个数的和
if (Math.abs(sum - target) < Math.abs(closestSum - target)) { // 更新最接近目标值的三个数的和
closestSum = sum;
}
if (sum > target) {
right--; // 如果当前和大于目标值，将右指针左移
} else if (sum < target) {
left++; // 如果当前和小于目标值，将左指针右移
} else {
return sum; // 如果当前和等于目标值，直接返回
}
}
}
return closestSum;
}
}
欢迎大家后台联系讨论。
（一份比较早的面试宝典，有兴趣的读者姥爷可以私信我领取！！！免费滴）
