leetcode16题解
题目描述
Given an integer array of length and an integer , find three integers in such that the sum is closest to .numsntargetnumstarget
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
思路
这道题和上一道题的思路基本完全一致。略作修改即可。 leetcode15
代码实现
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int size=nums.size();
int sum;
int dist_min=INT_MAX;
int res=INT_MAX;
sort(nums.begin(),nums.end());
//copy(nums.begin(),nums.end(),ostream_iterator<int>(cout," "));
//cout<<endl;
int lasti=INT_MIN;
int i=0;
while(i<size){
if(i!=size-2&&nums[i]==nums[i+1]){
for(int k=i+2;k<size;k++){
if(nums[i]+nums[i+1]+nums[k]==target){
return nums[i]+nums[i+1]+nums[k];
}
else if(dist_min>abs(nums[i]+nums[i+1]+nums[k]-target))
{
dist_min=abs(nums[i]+nums[i+1]+nums[k]-target);
res=nums[i]+nums[i+1]+nums[k];
}
}
}
do{
++i;
if(i==size-1) break;
}while(nums[i-1]==nums[i]);
if(i==size-1) break;
lasti=nums[i];
int lp,rp;
lp=0;
rp=size-1;
int lastlp=INT_MIN;
int lastrp=INT_MAX;
while(lp<i&&i<rp){
if(nums[lp]+nums[i]+nums[rp]<target){
if(dist_min>target-(nums[lp]+nums[i]+nums[rp]))
{
dist_min=target-(nums[lp]+nums[i]+nums[rp]);
res=nums[lp]+nums[i]+nums[rp];
}
lastlp=nums[lp];
while(lastlp==nums[++lp]&&lp<i&&i<rp)
;
}
else if(nums[lp]+nums[i]+nums[rp]>target){
if(dist_min>(nums[lp]+nums[i]+nums[rp])-target)
{
dist_min=(nums[lp]+nums[i]+nums[rp])-target;
res=nums[lp]+nums[i]+nums[rp];
}
lastrp=nums[rp];
while(lastrp==nums[--rp]&&lp<i&&i<rp)
;
}
else{
//copy(nums.begin(),nums.end(),ostream_iterator<int>(cout," "));
//cout<<endl;
return target;
//cout<<lp<<" "<<i<<" "<<rp<<" "<<endl;
lastlp=nums[lp];
while(lastlp==nums[++lp]&&lp<i&&i<rp)
;
}
}
}
return res;
}
};