首页 > 代码库 > 3Sum Closest
3Sum Closest
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).
直观思路：罗列所有三个数的组合，即组合问题，从S中选出三个数然后加起来和target做比对。（超时。。。）
思路2：其实这题和2sum类似，a+b+c=target 那么b+c=target-a，那么2sum的target为target-a
注意：排序之后，我们遍历num数组，为什么是遍历呢。。。
举个例子（-1,0,1,3,8），target=100
那么当start=0时，就固定了-1，然后从（0,1,3,8）求2sum，这个结果也即从5个数中求出三个数的和，这个和和target最接近。
那么当start=1，-1抛弃，然后固定0，从（1,3,8）中求2sum，这个结果也即从4个数中求出三个数的和，这个和和target最接近。
其实这就是罗列组合。
-1开头的组合（-1,0,1）（-1,0,3）（-1,0,8）（-1,1,3）（-1,1,8）（-1,3,8）
0开头的组合（0,1,3）（0,1,8）（0,3,8）
1开头的组合 （1,3,8）
我们用for循环来模拟这个选取组合，然后就是在剩下的数中找出最适合的2sum
代码：
class Solution {public: int threeSumClosest(vector<int> &num, int target) { if(num.size()<3) return 0; if(num.size()==3) return num[0]+num[1]+num[2]; int mindis=~(unsigned int)1>>1; int res=0; sort(num.begin(),num.end()); for(int start=0;start<num.size()-2;++start){ int sum2Target=target-num[start]; int mid=start+1; int end=num.size()-1; while(mid<end){ int sum2=num[mid]+num[end]; if(sum2>sum2Target){ --end; if(abs(sum2-sum2Target)<mindis){ mindis=abs(sum2-sum2Target); res=sum2+num[start]; } } else if(sum2<sum2Target){ ++mid; if(abs(sum2-sum2Target)<mindis){ mindis=abs(sum2-sum2Target); res=sum2+num[start]; } } else return sum2+num[start]; } } return res; }};
3Sum Closest