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