题目链接
注意点
- 和3Sum那道题的target是0，这道题是题目给定的
- 要先计算误差再移动指针
解法
解法一：做法类似3Sum那道题解法二，每次移动指针前先计算误差，如果误差为0，直接返回target即可。时间复杂度为O(n^2)
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int n = nums.size(),mytarget,i = n-1,j,k;
int minError = INT_MAX,ans = target;
while(i >= 2)
{
mytarget = target - nums[i];
j = 0;
k = i-1;
while(j < k)
{
int temp = nums[j]+nums[k];
if(temp < mytarget)
{
if(mytarget - temp < minError)
{
ans = nums[i]+nums[j]+nums[k];
minError = mytarget - temp;
}
j++;
}
else if(temp > mytarget)
{
if(temp - mytarget < minError)
{
ans = nums[i]+nums[j]+nums[k];
minError = temp - mytarget;
}
k--;
}
else
{
return target;
}
}
i--;
while(nums[i+1]==nums[i])
{
i--;
}
}
return ans;
}
};
小结
- 会做3Sum那道题，这题就不难