今天介紹的算法題是LeetCode 15題，3 Sum，也成三數求和問題。
鏈接
https://leetcode.com/problems/3sum/
難度
Medium
描述
給定一個整數的數組，要求尋找當中所有的a，b，c三個數的組合，使得三個數的和為0.注意，即使數組當中的數有重複，同一個數也只能使用一次。
Given an array nums of n integers, are there elements a , b , c innums such that a + b + c = 0? Find all unique triplets in the arraywhich gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
樣例
Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]]題解
這道題是之前LeetCode第一題2 Sum的提升版，在之前的題目當中，我們尋找的是和等於某個值的兩個數的組合。而這裡，我們需要找的是三個數。從表面上來看似乎差別不大，但是實際處理起來要麻煩很多。
暴力求解
我們先理一下思路，從最簡單的方法開始入手。這題最簡單的方法當然就是
暴力法，我們已經明確了要找的是三個數的和，既然數量確定了，就好辦了，我們直接枚舉所有三個數的組合，然後所有和等於0的組合就是答案。但是這裡有一個小問題，當我們找到了答案之後，我們並不能直接返回，因為數組當中重複的元素很有可能會導致答案的重複，我們必須要去掉這些重複的答案，保證答案當中每一個都是唯一的。那我們先對原數組做處理，去除掉其中重複的元素之後再來尋找答案可不可以呢？
很遺憾，這個想法很好，但是不可行。原因也很簡單，因為答案不能重複，但是答案裡的數是可以重複的。
舉個例子，比如數組是[-1, -1, 2, 0, -2]，那麼[-1, -1, 2]是一個答案，如果一開始就出去掉了重複的-1，那麼這個答案顯然就無法構成了。
唯一的解決方法是用容器來維護答案，保證容器內的答案是唯一的，不過這個會帶來額外的時間和空間開銷。所以，總體看來，暴力枚舉並不是個好方法，複雜度不低，如果使用C++和Java等語言的話，使用容器也很麻煩。
利用2 Sum
還有一個思路是利用之前的2 Sum的解法，在之前的2 Sum問題當中，我們通過巧妙地使用map，來達成了在 O(n) 複雜度內找到了所有和等於某個值的元素對。所以，我們可以先枚舉第一個數的大小，然後在剩下的元素當中進行2 Sum操作。
假設我們枚舉的數是a[i],那麼我們在剩下的元素當中做2 Sum，來尋找和等於-a[i]的兩個數。最後，將這三個數組成答案。如果遺忘2 Sum解法的同學可以點擊下方鏈接回到之前的文章。
這個方法看起來巧妙很多，但是還是逃不掉重複的問題。舉個例子：[-1, -1, -1, -1, -1, 2]。如果我們枚舉-1，那麼會出現多個[-1, -1, 2]的結果。所以我們依然免不了手動過濾重複的答案。不過利用2 Sum的解法要比暴力快一些，因為2 Sum的時間複雜度是
O(n) ，再乘上枚舉元素的複雜度，不考慮去重情況下的整體複雜度是 O(n^2)，要比枚舉的 O(n^3) 更優。我們利用2 sum寫出新的算法：
尺取法
這題的另一個解法是尺取法，也就是two pointers，也叫做兩指針算法。這個在我們之前的文章當中也有過介紹，有遺忘或者錯過的同學可以點擊下方的鏈接回顧一下。
尺取法的精髓是通過兩個指針控制一個區間，保證區間滿足一定的條件。在這題當中，我們要控制的條件其實是三個數的和。由於我們的指針數量是2，也就是說我們只有兩個指針，但是我們卻需要找到三個數組成的答案。顯然，我們直接使用尺取法是不行的。我們稍作變通就可以解決這個問題，就是第一個解法的思路，我們先枚舉一個數，然後再通過尺取法去尋找另外兩個數 。
使用尺取法需要我們根據現在區間內的信息，制定策略如何移動區間。顯然，如果區間裡的數雜亂無章，我們是很難知道應該怎麼維護區間的。所以我們首先對數組當中的元素進行排序，保證元素的有序性。區間裡的元素有序了，那麼我們就方便了。
假設我們當前枚舉的數是a[i]，那麼我們就需要找到另外的兩個數b和c，使得b + c = -a[i]。對於每一個i來說，這樣的b和c可能存在，也可能不存在，我們必須要尋找過了才知道。
和2 Sum一樣，為了優化時間複雜度，加快算法的效率，我們需要人為設置一些限制。我們限制b和c只能在a的右側，當然也可以限制在一左一右，總之，我們需要把這三個數的順序固定下來。因為三個數調換順序只會產生重複，所以我們固定順序可以避免重複。所以我們枚舉a的位置之後，在a的右側通過尺取法尋找另外兩個元素。
方法也很簡單，我們一開始設置b的位置是i+1, c的位置是n。如果b+c > -a，那麼說明兩者的和過大，因為b已經是最小值了，所以只能將c向左移動。如果b+c < -a，說明兩者的和過小，需要增大，所以應該將b往右側移動增大數值。如此往復，當這個區間遍歷完成之後，繼續移動a的位置，尋找下一組解，這裡需要注意，a需要跳過所有重複的數字，避免重複。
我們寫出代碼：
寫出代碼之後，我們來分析一下算法的複雜度。一開始的時候，我們對數組進行排序，眾所周知，排序的複雜度是 O(nlogn)。之後，我們枚舉了第一個數，開銷是 O(n) ，我們進行區間縮放的複雜度也是
O(n) ，所以整個主體程序的複雜度是 O(n^2) 。看似和上面一種方法區別不大，但是我們節省了set重複的判斷，由於hashset讀取會有時間開銷，所以雖然算法的量級上沒什麼差別，但是常數更小，真正運行起來這種算法要快很多。
這題官方給的難度是Medium，但實際上我覺得比一般的Medium要難上一些，代碼量也要大上一些。今天文章當中列舉的並不是全部的解法，其他的做法還有很多，比如對所有數進行分類，分成負數、零和正數，然後再進行組裝等等。感興趣的同學可以自己思考，看看還有沒有其他比較有趣的方法。
今天的文章就到這裡，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的支持是我最大的動力。
閱讀更多 樑唐晉漢周MOUT 的文章
