题目
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int len = nums.size();
int diff = target - nums[0]-nums[2]-nums[1];
int threeSumClosest = nums[0]+nums[2]+nums[1];
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
int k=len-1;
while(j<k){
if(abs(target - nums[i]-nums[j]-nums[k]) < diff){
diff = abs(target - nums[i]-nums[j]-nums[k]);
threeSumClosest = nums[i]+nums[j]+nums[k];
}
k--;
}
}
}
return threeSumClosest;
}
};
1986ms
优化
最关键的,不是无脑的k–,j++,而是分类讨论,大于了,就减小,k–,小于了,就增大,k++
在这里插入代码片
思考,出现顺序很重要
先判断是否是最小的,而不是先变更j和k的值
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int len = nums.size();
int diff = abs(target - nums[0]-nums[2]-nums[1]);
int threeSumClosest = nums[0]+nums[2]+nums[1];
for(int i=0;i<len;i++){
int j=i+1;
int k=len-1;
while(j<k){
if(abs(target - nums[i]-nums[j]-nums[k]) < diff){
diff = abs(target - nums[i]-nums[j]-nums[k]);
threeSumClosest = nums[i]+nums[j]+nums[k];
}
if(nums[i]+nums[j]+nums[k] == target){
return target;
}
else if(nums[i]+nums[j]+nums[k] > target){
k--;
}
else{
j++;
}
}
}
return threeSumClosest;
}
};