当前位置 博文首页 > 3Sum Closest_让代码改变世界：LeetCode 16
今天抽了点儿时间，来刷一道。
这是第16题了，这连续几道题的题型都比较类似，都是要求对数组排列组合，然后从中找出符合特定条件的一些组合，这种题算是一种比较大的题型吧，很多题目最终都转化成了这种题目，像第一题中找两个数使其和为给定值，还有后面那个最大水箱的题，到上面那个求三个数的和为特定值的所有组合。这些题目都是这样子的，通过前面的题目我们也知道了其一般“处理方式”，也就是先排序再处理的方法。当然每个题都有每个题的特点，具体的细节还是要自己处理的。不多说了，来看一下今天这道题吧：
Given an array?S?of?n?integers, find three integers in?S?such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
今天这道题是求数组中三个数字之和，要求与给定的一个数最接近。
首先，要把握这种题目的大方针，先看看排序有没有用，因为显然蛮力法的复杂度为O(n^3)，这样的算法八成是存在改进余地的，而改进的余地八成就是先排序再查找。我们采用和上一题接近的思路，先确定一个，然后对剩下的进行两端搜索，两端搜索是否能够进行取决于通过对两端点数据的判断能否决定移动端和其移动方向。现在这个题目可以采用“小了往大移大了往小移”准则来判断移动端和移动方向。
其次，确定了排序的有效性和移动策略，基本上这道题已经解决了，剩下的就是确定在移动过程中要做哪些判断以及怎样赋值了，由于这一题是要求和最接近的三个数，所以肯定是要记录最接近的三个数的和，然后不断扫描更新这个值。还有要注意的就是注意可以跳过的扫描项，重复的数字是否可以跳过，是否可以提前结束本次两端扫描？针对这一题，重复数字是可以跳过的额，两端扫描是不能提前终止的，也就是说必须扫完整个数组，至于为什么大家分析一下就可以了，简单的说就是通过判断当前的两端值不能确定中间是否有更好的组合。
最后，当然就是代码了，这里就采用本人的代码吧，因为大神的也类似，算法是完全一样的。
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
//获取数组长度
int len=nums.size();
//将数组排序
sort(nums.begin(),nums.end());
//定义返回结果
int result=nums[0]+nums[1]+nums[len-1];
//int result;
int lef=0,rig=0;
for(int i=0;i<len-2;++i)
{
lef=i+1;rig=len-1;
//cur_result=nums[i]+nums[lef]+nums[rig];
if(i!=0 && nums[i]==nums[i-1])continue;//跳过重复数字
while(lef<rig)
{
if(lef!=i+1&&nums[lef]==nums[lef-1]){lef++;continue;}//跳过重复数字
if(rig!=len-1&&nums[rig]==nums[rig+1]){rig--;continue;}//跳过重复数字
if(nums[i]+nums[lef]+nums[rig]==target)
return target;
else if(nums[i]+nums[lef]+nums[rig]<target)//小于target
{
result = abs(result-target)>abs(nums[i]+nums[lef]+nums[rig]-target)?
nums[i]+nums[lef]+nums[rig] : result;
lef++;
}
else if(nums[i]+nums[lef]+nums[rig]>target)//大于target
{
result = abs(result-target)>abs(nums[i]+nums[lef]+nums[rig]-target)?
nums[i]+nums[lef]+nums[rig] : result;
rig--;
}
}
}
return result;
}
};首先，从O(n^2)到O(n)。这所说的是一个泛指，也就是说可以通过排序来降低时间复杂度的情况，前面我们已经说过了，这种题的特点是排序后可以将两两组合的问题化简为两端搜索的问题，而能进行两端搜索的前面也说了，就是通过对两端点数据的判断能否决定移动端和其移动方向，复合这种特性的题目都有一种单调非减（或飞增）的性质，比如说第一题里面的两数字之和，和是一个单调的概念，我们可以借此来确定移动方向。而一些循环的就不能这样，比较说取余数运算，就算你对数据排序了，也不能确定该往那边移动。总之，先排序再搜索的思路是将一个O(n^2)的算法降低到了O(n)。
其次，二分查找。二分查找是产生O(logn)最常用的算法，所以如果将二分查找运用到本题，那可能就会产生O(nlogn)的算法。到底是否可行呢，我们先来分析一下二分查找都有什么性质：能进行二分查找的条件首先是排序数组，然后就是二分查找的有效性，什么时候二分查找是有效的呢？那就是不会漏数，也就是查找结果正确，一般的查找都是查找一个确定的数，这样显然是不会漏数的。但是本题呢，如果我们采用整体二端查找，中间采用二分查找的算法，是否可以如愿以偿得到O(nlogn)的算法呢？首先确定二分查找的有效性，我们要查一个什么数呢？我们要查的是一个最接近的数，二分查找能否找到最接近的数呢？答案是肯定的，我们的查找可以要么查找到所要求的结果，即找到了要找的数，要么可以找到其左边和右边的数，这样再判断一下就可以找到最接近的数了。其次找到最接近的数以后能否确定两端搜索的移动方向呢？这个就不可以了，假如这次找到的和比target小，那是否可以说明该将左端点往右移动呢？肯定不是的，因为中间的情况你是不知道的，也行将右边的往左移一个在二分查找就可以找到和为target的数呢，这种情况不能排除，也就是不能排序最左边的那个数。这样一来两端搜索就失效了，也就是说这种方法是不可行的。
最后，总结一句，先排序是为了实现两端搜索，两端搜索结合二分查找可能会有更好的效果，具体题目具体分析，分析方向就是这些了。
马上就要中秋节了，提前祝各位中秋快乐! 也祝每个被坚持梦想都能实现!
