题目：
给定一个包括 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 <= $10^3$
- $-10^3$ <= nums[i] <= $10^3$
- $-10^4$ <= target <= $10^4$
题解：
最先想三重暴力试一下
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int res = 0, n = nums.size(), diff = INT_MAX;
for (int i = 0; i < n - 2; i++)
{
for (int j = i + 1; j < n - 1; j++)
{
for (int k = j + 1; k < n; k++)
{
int sum = nums[i] + nums[j] + nums[k];
if (abs(sum - target) < diff)
{
diff = abs(sum - target);
res = sum;
}
}
}
}
return res;
}
};
然后发现，确实是会被卡部分测试样例，看来 O($n^3$)的算法复杂度是不可行的，得想办法优化一下，于是想到了双指针法，先排序，然后固定一个数，另外两个数用双指针法，这样时间复杂度就是$O(n^2)$了
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int res = 0, n = nums.size(), diff = INT_MAX;
sort(nums.begin(), nums.end());
for(int i=0;i<n-1;i++){
int l = i+1, r = n-1;
while(l<r){
int sum = nums[i] + nums[l] + nums[r];
if(abs(sum-target)<diff){
diff = abs(sum-target);
res = sum;
}
if(sum<target) l++;
if(sum>target) r--;
if(sum==target) return res;
}
}
return res;
}
};