力扣16.最接近的三数之和（双指针）

给你一个长度为 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.暴力+剪枝（刚好不超时1000~1500ms），剪枝的主要内容是：a.第三层循环从尾部开始遍历，当这次的差值（current_difference）大于上次的差值（previous_difference）时，就可以停止第三层循环的遍历了，因为再往左走差值只会越来越大。b.前两层的遍历过程中，可以跳过相同元素。

 1 class Solution {
 2 public:
 3     int threeSumClosest(vector<int>& nums, int target) {
 4         sort(nums.begin(),nums.end());
 5         int similarity; //记录最相似的值
 6         int minimum_difference=INT32_MAX; //记录最小差值
 7         for (int i=0;i<nums.size()-2;i++){
 8             if (i>0&&nums[i]==nums[i-1])
 9                 continue;
10             int goal=target-nums[i];
11             for (int left=i+1;left<nums.size()-1;++left){
12                 if (left>i+1&&nums[left]==nums[left-1])
13                     continue;
14                 int previous_difference=INT32_MAX; //记录上一次遍历的差值
15                 int current_difference; //记录当前差值
16                 for (int right=nums.size()-1;right>left;right--){
17                     current_difference=abs(goal-nums[left]-nums[right]);
18                     if (current_difference>previous_difference)
19                         break;
20                     if (current_difference<=minimum_difference){
21                         minimum_difference=abs(goal-nums[left]-nums[right]);
22                         similarity=nums[i]+nums[left]+nums[right];
23                     }
24                     if (minimum_difference==0){
25                         return target;
26                     }
27                     previous_difference=current_difference;
28                 }
29             }
30         }
31         return similarity;
32     }
33 };