编程题-最接近的三数之和

题目：

给你一个长度为 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;}};// 枚举 afor (int i = 0; i < n; ++i) {// 保证和上一次枚举的元素不相等if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 使用双指针枚举 b 和 cint 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)。