思路:
类似3sum/2sum利用双指针。
不同在于,这里只要计算总和就可以了,这部分更加简单。
总体的思路是:
先预先排序,加快搜索速度。
确定left,然后用mid/right扫描数组。
当总和与target的距离变小时,更新数据。
接着,如果正好==target 直接返回,如果>target ,说明大了,right--,反之,mid++。
注意:
1.返回值mmin初始化最好是nums[0]+nums[1]+nums[2],因为可能会出现只有三个元素的情况。如果不这样处理,后面可能不会执行mmin的更新。(即返回的可能是你的其他初始值)
2.要考虑sum==target的情况。如果一开始就处理这个可能性,不要忘了mid和right经过调整后也会出现这种情况,比较优雅的写法是直接放在while(mid<right)作为第三种情况处理。
代码:(C++)
int threeSumClosest(vector<int>& nums, int target) {
int mmin=nums[0]+nums[1]+nums[2]; //debug:mmin需要初始化,因为下面有限制条件才跳进去更新,如果正好是三个数且正好符合就会遗漏
int len=nums.size();
sort(nums.begin(),nums.end());
for(int left=0;left<len-2;left++){
int mid=left+1;
int right=len-1;
while(mid<right){
int tmp_sum=nums[left]+nums[mid]+nums[right];
//距离更近了,就更新记录
if(abs(target-tmp_sum)<abs(target-mmin)){
mmin=tmp_sum;
}
if(tmp_sum<target){ //太少了,mid往右移
mid++;
}else if(tmp_sum>target){ //太多了,right往左移
right--;
}else{ //debug:这部分不能放在上面,因为有可能在调整了指针后也会正好符合的情况。
mmin=nums[left]+nums[mid]+nums[right];
return mmin;
}
}
}
return mmin;
}
网友评论