力扣?
?思路
排序+双指针
枚举第一个数a，对剩下的两个元素b，c，希望它们的和最接近target-a
1.如果它们在原数组中枚举的范围没有任何规律可言，只能用两重循环来枚举所有情况
? ? ? ?->考虑对数组升序排序
2.假设数组长度为n，先枚举a,在数组中的位置为i
? ?在[i+1,n)枚举b，c
3.用j，l分别表示指向b和c的指针，初始时，j指向位置i+1;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?l指向位置n-1;
4.如果a+b+c>target，l--;
? ?如果a+b+c<=target,k++;
简单证明：
不失一般性，只考虑a+b+c>target的情况：
如果l不变,k向右移，则a+b+c变大，远离target的值，不可能符合条件,
l左移，a+b+c变小，可能靠近target,也可能远离target（小于target）
所以，l左移为当前的最优解。
代码
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int j,l;
int min_abs_minus=INT_MAX;//定义绝对值之差的最小值
int temp_abs_minus;//定义当前绝对值之差
int res;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-2;i++)//固定住i，移动j，l
{
j=i+1;
l=nums.size()-1;
while(j<l)
{
if(nums[i]+nums[j]+nums[l]<target)
{
temp_abs_minus=target-nums[i]-nums[j]-nums[l];
if(temp_abs_minus<min_abs_minus)
{
min_abs_minus=temp_abs_minus;
res=nums[i]+nums[j]+nums[l];
}
j++;
}
else if(nums[i]+nums[j]+nums[l]>target)
{
temp_abs_minus=nums[i]+nums[j]+nums[l]-target;
if(temp_abs_minus<min_abs_minus)
{
res=0;
min_abs_minus=temp_abs_minus;
res=nums[i]+nums[j]+nums[l];
}
l--;
}
else
{
return target;
}
}
}
return res;
}
};小技巧
1.vector数组排序
sort(num.begin(),num.end());
2.对撞双指针
left=左边界;
right=右边界;
while(left<right)
{
...
left++;
...
right--;
}