2021-6-29 16. 最接近的三数之和（固定一位+双指针）

本文主要是介绍2021-6-29 16. 最接近的三数之和（固定一位+双指针），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注：
该题不同于leetcode15题，不需要考虑重复的情况。

题目：
给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

题解：
我们首先考虑枚举第一个元素 a，对于剩下的两个元素 b 和 c，我们希望它们的和最接近 target−a。对于 b 和 c，如果它们在原数组中枚举的范围（既包括下标的范围，也包括元素值的范围）没有任何规律可言，那么我们还是只能使用两重循环来枚举所有的可能情况。因此，我们可以考虑对整个数组进行升序排序，这样一来：

假设数组的长度为 n，我们先枚举 a，它在数组中的位置为 i；
为了防止重复枚举，我们在位置[i+1,n) 的范围内枚举 b 和 c。

当我们知道了 b 和 c 可以枚举的下标范围，并且知道这一范围对应的数组元素是有序（升序）的，那么我们是否可以对枚举的过程进行优化呢？

答案是可以的。借助双指针，我们就可以对枚举的过程进行优化。我们用 pb和pc分别表示指向 b 和 c 的指针，初始时，pb指向位置 i+1，即左边界；pc指向位置 n-1，即右边界。在每一步枚举的过程中，我们用 a+b+c 来更新答案，并且：

如果a+b+c≥target，那么就将 pc向左移动一个位置；
如果 a+b+c<target，那么就将 pb向右移动一个位置。

这是为什么呢？我们对 a+b+c≥target 的情况进行一个详细的分析：

如果a+b+c≥target，并且我们知道 pb到 pc这个范围内的所有数是按照升序排序的，那么如果 pc不变而 pb向右移动，那么 a+b+c 的值就会不断地增加，显然就不会成为最接近 target 的值了。因此，我们可以知道在固定了 pc的情况下，此时的 pb就可以得到一个最接近 target 的值，那么我们以后就不用再考虑 pc了，就可以将 pc向左移动一个位置。

复杂度分析：
时间复杂度 O(N²)：其中固定指针k循环复杂度O(N)，双指针 i，j 复杂度 O(N)。
空间复杂度 O(1)：指针使用常数大小的额外空间。

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {int result=INT_MAX;int temp=INT_MAX;sort(nums.begin(),nums.end());for(int first=0;first<nums.size();first++){for(int second=first+1;second<nums.size();second++){int third=nums.size()-1;while(second<third){if(abs(target-nums[first]-nums[second]-nums[third])<temp){temp=abs(target-nums[first]-nums[second]-nums[third]);result=nums[first]+nums[second]+nums[third];}if(nums[first]+nums[second]+nums[third]>target){third--;}else if(nums[first]+nums[second]+nums[third]<target){second++;}else{return target;}}}}return result;}
};