LeetCode 16. 最接近的三数之和
原题链接
中等
作者:
李哥
,
2020-06-13 21:31:02
,
所有人可见
,
阅读 706
优化一下
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(begin(nums), end(nums));
int ans=nums[0]+nums[1]+nums[2];
int L=0,R=0,sum=0,min=0,max=0;
for (int i = 0; i < nums.size(); i++) {
L=i+1;R=nums.size()-1;
if(i>0&&nums[i]==nums[i-1]) continue; //对i去重
while(L<R) {
min=nums[i]+nums[L]+nums[L+1];
if(target<min&&abs(min-target)<abs(ans-target)) {
ans=min; break;
}
max=nums[i]+nums[R]+nums[R-1];
if(target>max&&abs(max-target)<abs(ans-target)) {
ans=max; break;
}
sum=nums[i]+nums[L]+nums[R];
if(sum==target) return sum;
else if(sum>target) {
R--;
while(L<R&&nums[R]==nums[R+1]) R--; //对L去重
}
else {
L++;
while(L<R&&nums[L]==nums[L-1]) L++; //对R去重
};
if(abs(sum-target)<abs(ans-target)) ans=sum;
}
}
return ans;
}
};