编程题-最接近的三数之和
题目：
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
解法一（排序+双指针）：
题目要求找到与目标值 target 最接近的三元组，这里的「最接近」即为差值的绝对值最小。我们可以考虑直接使用三重循环枚举三元组，找出与目标值最接近的作为答案，时间复杂度为 O(N^3)。然而本题的 N 最大为 1000，会超出时间限制。
我们首先枚举第一个元素 a1，对于剩下的两个元素 a2和 a3，希望它们的和最接近target−a1。对于 a2 和 a3，如果它们在原数组中枚举的范围（既包括下标的范围，也包括元素值的范围）没有任何规律可言，那么我们还是只能使用两重循环来枚举所有的可能情况。因此，我们可以考虑对整个数组进行升序排序，这样一来
-
假设数组的长度为 n，我们先枚举 a1，它在数组中的位置为 i；
-
为了防止重复枚举，我们在位置 [i+1,n) 的范围内枚举 a2 和 a3。
当我们知道了a2和a3可以枚举的下标范围，并且知道这一范围对应的数组元素是有序（升序）的，那么我们是否可以对枚举的过程进行优化呢？
借助双指针对枚举的过程进行优化，我们用a2和a3作为双指针，初始时，a2指向位置i+1，即左边界，a3指向位置n-1，即右边界。在每一步枚举过程中，我们采用a1+a2+a3来更新答案，并且
-
如果 a1+a2+a3≥target，那么就将 a3 向左移动一个位置；
-
如果 a1+a2+a3<target，那么就将 a2 向右移动一个位置。
这是为什么呢，我们对 a1+a2+a3≥target的情况进行详细的分析：
如果a1+a2+a3≥target，并且我们知道a2和a3这个范围是按照升序排列的，那么如果a3不变而移动a2向右，那么a1+a2+a3的值就会不断地增加，显然就不会成为最接近target的值了。因此，我们可以知道在固定a3的情况下，此时的a2就可以得到一个最接近target的值了，那么我们以后就不用再考虑a3了，就可以将a3向左移动一个位置。
同样地，a1+a2+a3<target 时，如果a2不变而a3向左移动，那么a1+a2+a3的值就会不断地减小，显然就不会成为最接近target的值了。因此，我们可以知道固定了a2的情况下，此时的a3就可以得到一个最接近target的值，那么我们以后就不用再考虑a2了，就可以将a2向右移动一个位置。
实际上，a2和a3就表示我们当前选择的数的范围，而每一次枚举的过程中，我们尝试边界上的两个元素，根据它们与target的值的关系，选择【抛弃】左边界的元素还是右边界的元素，从而减少了枚举的范围。这种思路与【盛最多水的容器】中的双指针解法也是类似的。当我们枚举，a1,a2,a3 中任意元素并移动指针时，可以直接将其移动到下一个与这次枚举得到的不相同的元素，减少枚举的次数，如下代码为：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int best = 1e7;
// 根据差值的绝对值来更新答案
auto update = [&](int cur) {
if (abs(cur - target) < abs(best - target)) {
best = cur;
}
};
// 枚举 a
for (int i = 0; i < n; ++i) {
// 保证和上一次枚举的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 使用双指针枚举 b 和 c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果和为 target 直接返回答案
if (sum == target) {
return target;
}
update(sum);
if (sum > target) {
// 如果和大于 target，移动 c 对应的指针
int k0 = k - 1;
// 移动到下一个不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
// 如果和小于 target，移动 b 对应的指针
int j0 = j + 1;
// 移动到下一个不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
};时间复杂度：O(N2)，其中 N 是数组 nums 的长度。我们首先需要 O(NlogN) 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(N) 枚举 a，双指针 O(N) 枚举 b 和 c，故一共是 O(N2)。
空间复杂度：O(logN)。排序需要使用 O(logN) 的空间。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，此时空间复杂度为 O(N)。
下面代码是笔者在编程时所写的，虽然时间复杂度没有超限，但是相比上面代码在时间复杂度上面仍然是消耗时间比较大的，但是空间复杂度上面比上面代码占用消耗是较小的。其中第二层循环中思路也是：如果和小于target，则移动a2向右移动，进入下一次循环；如果和大于target，则移动a3向左移动，执行while循环，实现原理通过增加条件判断语句使得双指针（左边界指针、右边界指针）两个指针朝着相遇的方向进行移动（减少时间复杂度，防止重复遍历），但是阅读理解代码起来较为复杂，同样是作为正确的解决思路与上面方法进行对比，如下为笔者代码：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
//定义输出结果result值
int min_value = 1000000, length=nums.size();
int result=0;
//将nums数组由小到大重新进行排序
sort(nums.begin(), nums.end());
//循环遍历查找满足条件要求的结果
for(int a1=0; a1<length-2; a1++){
if(a1>1 && nums[a1]==nums[a1-1]){
continue;
}
for(int a2=a1+1; a2<length-1;a2++){
if(a2>a1+1 && nums[a2]==nums[a2-1]){
continue;
}
int a3 = length-1;
//如果和小于target，则移动a2向右移动（进入下一层循环）
if(nums[a1]+nums[a2]+nums[a3]<target){
result=min_value>abs(nums[a1]+nums[a2]+nums[a3]-target)?(nums[a1]+nums[a2]+nums[a3]):result;
min_value = min(abs(nums[a1]+nums[a2]+nums[a3]-target), min_value);
continue;
}
while(a2<a3){
if(nums[a1]+nums[a2]+nums[a3]<target){
result=min_value>abs(nums[a1]+nums[a2]+nums[a3]-target)?(nums[a1]+nums[a2]+nums[a3]):result;
min_value = min(abs(nums[a1]+nums[a2]+nums[a3]-target), min_value);
result=min_value>abs(nums[a1]+nums[a2]+nums[a3+1]-target)?(nums[a1]+nums[a2]+nums[a3+1]):result;
min_value = min(abs(nums[a1]+nums[a2]+nums[a3+1]-target), min_value);
break;
}
//如果和大于target，则移动a3向左移动（执行while循环）
else{
result=min_value>abs(nums[a1]+nums[a2]+nums[a3]-target)?(nums[a1]+nums[a2]+nums[a3]):result;
min_value = min(abs(nums[a1]+nums[a2]+nums[a3]-target), min_value);
a3--;
}
}
}
}
return result;
}
};笔者小记：
1、借助双指针对枚举的过程进行优化，降低多重循环导致的时间复杂度。对于本题，时间复杂度可由O(N^3)降低至O(N^2)。