735
阿裏雲 技術社區[雲棲]
LeetCode之K sum problem
做過leetcode的人都知道, 裏麵有2sum, 3sum(closest), 4sum等問題, 這些也是麵試裏麵經典的問題, 考察是否能夠合理利用排序這個性質, 一步一步得到高效的算法. 經過總結, 本人覺得這些問題都可以使用一個通用的K sum求和問題加以概括消化, 這裏我們先直接給出K Sum的問題描述和算法(遞歸解法), 然後將這個一般性的方法套用到具體的K, 比如leetcode中的2Sum, 3Sum, 4Sum問題. 同時我們也給出另一種哈希算法的討論.
leetcode求和問題描述(K sum problem)：
K sum的求和問題一般是這樣子描述的：給你一組N個數字(比如 vector<int> num), 然後給你一個常數(比如 int target) ，我們的goal是在這一堆數裏麵找到K個數字，使得這K個數字的和等於target。
注意事項(constraints):
注意這一組數字可能有重複項：比如 1 1 2 3 , 求3sum, 然後 target = 6, 你搜的時候可能會得到 兩組1 2 3, 1 2 3，1 來自第一個1或者第二個1, 但是結果其實隻有一組，所以最後結果要去重。
K Sum求解方法, 適用leetcode 2Sum, 3Sum, 4Sum：
方法一： 暴力，就是枚舉所有的K-subset, 那麼這樣的複雜度就是 從N選出K個，複雜度是O(N^K)
方法二： 排序，這個算法可以考慮最簡單的case, 2sum，這是個經典問題，方法就是先排序，然後利用頭尾指針找到兩個數使得他們的和等於target,
這個2sum算法網上一搜就有，這裏不贅述了，給出2sum的核心代碼：
02
|
int i
= starting; //頭指針
|
03
|
int j
= num.size() - 1; //尾指針
|
05
|
int sum
= num[i] + num[j];
|
07
|
store
num[i] and num[j] somewhere;
|
08
|
if(we
need only one such pair of numbers)
|
2sum的算法複雜度是O(N log N) 因為排序用了N log N以及頭尾指針的搜索是線性的，所以總體是O(N log N)，好了現在考慮3sum, 有了2sum其實3sum就不難了，這樣想：先取出一個數，那麼我隻要在剩下的數字裏麵找到兩個數字使得他們的和等於(target – 那個取出的數)就可以了吧。所以3sum就退化成了2sum, 取出一個數字，這樣的數字有N個，所以3sum的算法複雜度就是O(N^2 ), 注意這裏複雜度是N平方，因為你排序隻需要排一次，後麵的工作都是取出一個數字，然後找剩下的兩個數字，找兩個數字是2sum用頭尾指針線性掃，這裏很容易錯誤的將複雜度算成O(N^2
log N)，這個是不對的。我們繼續的話4sum也就可以退化成3sum問題，那麼以此類推，K-sum一步一步退化，最後也就是解決一個2sum的問題，K sum的複雜度是O(n^(K-1))。 這個界好像是最好的界了，也就是K-sum問題最好也就能做到O(n^(K-1))複雜度，之前有看到過有人說可以嚴格數學證明，這裏就不深入研究了。
K Sum (2Sum, 3Sum, 4Sum) 算法優化(Optimization)：
這裏講兩點，第一，注意比如3sum的時候，先整體排一次序，然後枚舉第三個數字的時候不需要重複， 比如排好序以後的數字是 a b c d e f, 那麼第一次枚舉a, 在剩下的b c d e f中進行2 sum, 完了以後第二次枚舉b, 隻需要在 c d e f中進行2sum好了，而不是在a c d e f中進行2sum, 這個大家可以自己體會一下，想通了還是挺有幫助的。第二，K Sum可以寫一個遞歸程序很優雅的解決，具體大家可以自己試一試。寫遞歸的時候注意不要重複排序就行了。
K Sum (2Sum, 3Sum, 4Sum) 算法之3sum源代碼(不使用std::set)和相關開放問題討論：
因為已經收到好幾個網友的郵件需要3sum的源代碼, 那麼還是貼一下吧, 下麵的代碼是可以通過leetcode OJ的代碼(又重新寫了一遍, 於Jan, 11, 2014 Accepted), 就當是K sum的完整的一個case study吧, 順便解釋一下上麵的排序這個注意點, 同時我也有關於結果去重的問題可以和大家討論一下,
也請大家集思廣益, 發表意見, 首先看源代碼如下：
03
|
vector<vector<int>
> threeSum(vector<int>
&num) {
|
04
|
vector<vector<int>
> vecResult;
|
08
|
vector<int>
vecTriple(3, 0);
|
09
|
sort(num.begin(),
num.end());
|
10
|
int iCurrentValue
= num[0];
|
11
|
int iCount
= num.size() - 2; //
(1) trick 1
|
12
|
for(int i
= 0; i < iCount; ++i) {
|
13
|
if(i
&& num[i] == iCurrentValue) { //
(2) trick 2: trying to avoid repeating triples
|
17
|
vecTriple[0]
= num[i];
|
19
|
int k
= num.size() - 1;
|
21
|
int iSum
= num[j] + num[k];
|
22
|
if(iSum
+ vecTriple[0] == 0) {
|
23
|
vecTriple[1]
= num[j];
|
24
|
vecTriple[2]
= num[k];
|
25
|
vecResult.push_back(vecTriple); //
copy constructor
|
29
|
else if(iSum
+ vecTriple[0] < 0)
|
34
|
iCurrentValue
= num[i];
|
36
|
//
trick 3: indeed remove all repeated triplets
|
37
|
//
trick 4: already sorted, no need to sort the triplets at all, think about why?
|
38
|
vector<
vector<int>
>::iterator it = unique(vecResult.begin(), vecResult.end());
|
39
|
vecResult.resize(
distance(vecResult.begin(), it) );
|
首先呢, 在K Sum問題中都有個結果去重的問題, 前文也說了, 如果輸入中就有重複元素的話, 最後結果都需要去重, 去重有好幾個辦法, 可以利用std::set的性質(如leetcode上3sum的文章, 但是他那個文章的問題是, set沒用好, 導致最終複雜度其實是O(N^2 * log N), 而非真正的O(N^2) ), 可以利用排序(如本文的方法)等, 去重本身不難, 難的是不利用任何排序或者std::set直接得到沒有重複的triplet結果集. 本人試圖通過已經排好序這個性質來做到這一點(試圖不用trick
3和4下麵的兩條語句), 但是經過驗證這樣的代碼(沒有trick 3, 4下麵的兩行代碼, 直接return vecResult)也不能保證結果沒有重複，於是不得不加上了trick 3, 4，還是需要通過在結果集上進一步去重. 筆者對於這個問題一直沒有很好的想法, 希望這裏的代碼能拋磚引玉,
大家也討論一下有沒有辦法, 或者利用排序的性質或者利用其它方法, 直接得到沒有重複元素的triplet結果集, 不需要去重這個步驟.
那麼還是解釋一下源代碼裏麵有四個trick, 以及筆者試圖不利用任何std::set或者排序而做到去重的想法.
第一個無關緊要順帶的小trick 1, 是說我們排好序以後, 隻需要檢測到倒數第三個數字就行了, 因為剩下的隻有一種triplet 由最後三個數字組成. 接下來三個trick都是和排序以及最後結果的去重問題有關的, 我一起說.
筆者為了達到不需要在最後的結果集做額外的去重, 嚐試了以下努力: 首先對輸入數組整體排序, 然後使用之前提到的3sum的算法, 每次按照順序先定下triplet的第一個數字, 然後在數組後麵尋找2sum, 由於已經排好序, 為了防止重複, 我們要保證triplet的第一個數字沒有重複, 舉個例子, -3, – 3, 2, 1, 那麼第二個-3不應該再被選為我們的第一個數字了, 因為在第一個-3定下來尋找2
sum的時候, 我們一定已經找到了所有以-3為第一個數字的triplet(trick 2). 但是這樣做盡管可以避免一部分的重複, 但是還有另一種重複無法避免: -3, -3, -3, 6, 那麼在定下第一個-3的時候, 我們已經有兩組重複triplet <-3, -3, 6>， 如何在不使用std::set的情況下避免這類重複, 筆者至今沒有很好的想法. 大家有和建議?
望不吝賜教！
Hash解法(Other)：
其實比如2sum還是有線性解法的，就是用hashmap, 這樣你check某個值存在不存在就是常數時間，那麼給定一個sum, 隻要線性掃描, 對每一個number判斷sum – num存在不存在就可以了。注意這個算法對有重複元素的序列也是適用的。比如 2 3 3 4 那麼hashtable可以使 hash(2) = 1; hash(3) = 1, hash(4) =1其他都是0, 那麼check的時候，掃到兩次3都是check sum – 3在不在hashtable中，注意最後返回所有符合的pair的時候也還是要去重。這樣子推廣的話
3sum 其實也有O(N^2)的類似hash算法，這點和之前是沒有提高的，但是4sum就會有更快的一個算法。
4sum的hash算法：
O(N^2)把所有pair存入hash表，並且每個hash值下麵可以跟一個list做成map， map[hashvalue] = list，每個list中的元素就是一個pair, 這個pair的和就是這個hash值，那麼接下來求4sum就變成了在所有的pair value中求 2sum，這個就成了線性算法了，注意這裏的線性又是針對pair數量(N^2)的線性，所以整體上這個算法是O(N^2)，而且因為我們掛了list, 所以隻要符合4sum的我們都可以找到對應的是哪四個數字。
到這裏為止有人提出這個算法不對 (感謝Jun提出這點!! See the comment below), 因為這裏的算法似乎無法檢查取出來的四個數字是否有重複的, 也就是說在轉換成2sum問題得到的那些個pair中, 有可能會有重複元素, 比如說原來數組中的第一個元素其實是重複了兩次才使得4 sum滿足要求, 那麼這樣得到的四元組(四個數字的和等於給定的值), 其實隻有三個原數組元素, 其中第一個元素用了兩次, 那麼這樣就不對了. 如果僅從我上麵的描述來看, 確實是沒有辦法檢查重複的, 但是仔細想想我們隻要在map中存pair的的時候記錄下的不是原數組對應的值,
而是原數組的id,就可以避免這個問題了. 更加具體的, map[hashvalue] = list, 每個list的元素就是一個pair, 這個pair<int, int> 中的pair是原來的array id, 使得這兩個id對應到元素組中的元素值的和就是這個hash值. 那麼問題就沒有了, 我們在轉換成的2sum尋找所有pair value的2sum的同時要檢查最後得到的四元組<id1, id2, id3, id4>沒有重複id. 這樣問題就解決了.
結束語：
這篇文章主要想從一般的K sum問題的角度總結那些比較經典的求和問題比如leetcode裏麵的2sum, 3sum(closest), 4sum等問題, 文章先直接給出K Sum的問題描述和算法(遞歸解法), 然後將這個一般性的方法套用到具體的K, 比如leetcode中的2Sum, 3Sum, 4Sum問題. 同時我們也給出另一種哈希算法的討論. 那麼這篇文章基本上還是自己想到什麼寫什麼，有疏忽不對的地方請大家指正，也歡迎留言討論，如果需要源代碼，請留言或者發郵件到info@tech-wonderland.net
最後更新：2017-04-03 12:54:36