(一)前言
做過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
}
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;
}
};
