(一)前言
做过leetcode的人都知道, 里面有2sum, 3sum(closest), 4sum等问题, 这些也是面试里面经典的问题, 考察是否能够合理利用排序这个性质, 一步一步得到高效的算法. 经过总结, 本人觉得这些问题都可以使用一个通用的K sum求和问题加以概括消化, 这里我们先直接给出K Sum的问题描述和算法(递归解法), 然后将这个一般性的方法套用到具体的K, 比如leetcode中的2Sum, 3Sum, 4Sum问题.
还有求最接近target的2、3、4个数，是上述问题的变形，思路变化不大。
（二）leetcode求和问题描述(K sum problem)：
K sum的求和问题一般是这样子描述的：给你一组N个数字(比如 vector
（三）注意事项
?
注意这一组数字可能有重复项：比如 1 1 2 3 , 求3sum, 然后 target = 6, 你搜的时候可能会得到 两组1 2 3, 1 2 3，1 来自第一个1或者第二个1, 但是结果其实只有一组，所以最后结果要去重。
去重的方法有两个：
（1）前后移动探测，发现重复数字
?
//寻找其他可能的2个数，顺带去重
while (++p < q && num[p-1] == num[p])
{
//do nothing
}
while (--q > p && num[q+1] == num[q])
{
//do noghing
}
（2）借助STL容器 set：set
?
set不允许有重复的值出现。
（四）K Sum求解方法, 适用leetcode 2Sum, 3Sum, 4Sum
方法一： 暴力，就是枚举所有的K-subset, 那么这样的复杂度就是 从N选出K个，复杂度是O(N^K)
方法二： 排序+贪心
这种方法适用于2sum，3sum， 3sum cloest(找3个数的和最接近target),4sum ,4sum cloest（4个数的和最接近target）问题
总体思路：
2sum：先排序，默认非递减排序，固定0个数，头尾双指针选定2个数，利用贪心策略（sum-target>0,则尾指针左移，相反头指针右移，很容易证明），直至找到sum=target
类似于二分查找，时间复杂度O（N）
3 sum：先排序，固定1个数（外层一个for循环遍历），再采用头尾双指针选定两个数，仍然采用贪心策略移动指针，得到3sum =target
时间复杂度O（N*N）
3 sum cloest:原理同3sum，只不过多了比较，下面有代码贴出，看一眼就明白，时间复杂度O（N*N）
4 sum：由于贪心策略只适用于双指针，所以这里需要固定2个数，怎么固定？双层for循环遍历！！！再引入头尾双指针，时间复杂度O（N*N*N）
4sum cloest：同上 ，时间复杂度O（N*N*N）
?
//2 sum
int i = starting; //头指针
int j = num.size() - 1; //尾指针
while(i < j) {
int sum = num[i] + num[j];
if(sum == target) {
store num[i] and num[j] somewhere;
if(we need only one such pair of numbers)
break;
otherwise
do ++i, --j;
}
else if(sum < target)
++i;
else
--j;
}
//3 sum
//对原数组非递减（递增）排序
InsertSort(num,num.size());
for (int i = 0; i < num.size(); ++i)
{
//去重
if (i != 0 && num[i] == num[i-1])
continue;
int p = i + 1, q = num.size() - 1;
int sum = 0;
//收缩法寻找第2，第3个数
while (p < q)
{
sum = num[i] + num[p] + num[q];
if (sum == 0)
{
vector
newRes;
newRes.push_back(num[i]);
newRes.push_back(num[p]);
newRes.push_back(num[q]);
InsertSort(newRes,newRes.size());
res.push_back(newRes);
//寻找其他可能的2个数，顺带去重
while (++p < q && num[p-1] == num[p])
{
//do nothing
}
while (--q > p && num[q+1] == num[q])
{
//do noghing
}
}
else if (sum < 0) //和太小，p向后移动
{
++p;
}
else //和过大，q向前移动
{
--q;
}
}
}
// 3 sum cloest
class Solution {
public:
int threeSumClosest(vector
&num, int target) {
int index;
bool flag=true;
sort(num.begin(),num.end());
if(num.at(0)+num.at(1)+num.at(2)>target)
index=num.at(0)+num.at(1)+num.at(2)-target ;
else
{
index=target-(num.at(0)+num.at(1)+num.at(2));
flag=false;
}
for (int i = 0; i < num.size(); ++i)
{
int p = i + 1, q = num.size() - 1;
int sum=0;
while (p < q)
{
sum = num[i] + num[p] + num[q];
if (sum == target)
{
return sum;
}//if
else if (sum < target) //和太小，p向后移动
{
++p;
if(target-sum
//4 sum
class Solution
{
public:
vector
> fourSum(vector
&num, int target) { // Note: The Solution object is instantiated only once. vector
> res; int numlen = num.size(); if(num.size()<4)return res; sort(num.begin(),num.end()); set
> tmpres; for(int i = 0; i < numlen; i++) { for(int j = i+1; j < numlen; j++) { int begin = j+1; int end = numlen-1; while(begin < end) { int sum = num[i]+ num[j] + num[begin] + num[end]; if(sum == target) { vector
tmp; tmp.push_back(num[i]); tmp.push_back(num[j]); tmp.push_back(num[begin]); tmp.push_back(num[end]); tmpres.insert(tmp); begin++; end--; }else if(sum
>::iterator it = tmpres.begin(); for(; it != tmpres.end(); it++) res.push_back(*it); return res; } };
?
?
?
?
?
?
?
?
?