(一)前言
做过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<int> num), 然后给你一个常数(比如 int target) ，我们的goal是在这一堆数里面找到K个数字，使得这K个数字的和等于target。
（三）注意事项
注意这一组数字可能有重复项：比如 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<vector<int> >
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 sumint 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;otherwisedo ++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<int> 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;}}}<span style="font-family: Arial, Helvetica, sans-serif;">// 3 sum cloestclass Solution {</span>public:int threeSumClosest(vector<int> &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;}//ifelse if (sum < target) //和太小，p向后移动{++p;if(target-sum<index){index=target-sum;flag=false;}}else//和过大，q向前移动{–q;if(sum-target<index){index=sum-target;flag=true;}}//else}//while}//forif(flag)return index+target;elsereturn target-index;}};//4 sumclass Solution{public:vector<vector<int> > fourSum(vector<int> &num, int target) {// Note: The Solution object is instantiated only once.vector<vector<int>> res;int numlen = num.size();if(num.size()<4)return res;sort(num.begin(),num.end());set<vector<int>> 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<int> 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<target)begin++;elseend–;}}}set<vector<int>>::iterator it = tmpres.begin();for(; it != tmpres.end(); it++)res.push_back(*it);return res;}};
即使爬到最高的山上，一次也只能脚踏实地地迈一步。
