​LeetCode刷題實戰15題: 三數之和

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做三數之和 ，我們先來看題面：

https://leetcode.com/problems/3sum/

描述

給定一個整數的數組，要求尋找當中所有的a，b，c三個數的組合，使得三個數的和為0.注意，即使數組當中的數有重複，同一個數也只能使用一次。

Given an array nums of n integers, are there elements a , b , c in
nums such that a + b + c = 0? Find all unique triplets in the array
which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

樣例

給定數組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

題解

這道題是之前LeetCode第一題2 Sum的提升版，在之前的題目當中，我們尋找的是和等於某個值的兩個數的組合。而這裡，我們需要找的是三個數。從表面上來看似乎差別不大，但是實際處理起來要麻煩很多。

  暴力求解  

我們先理一下思路，從最簡單的方法開始入手。這題最簡單的方法當然就是暴力法，我們已經明確了要找的是三個數的和，既然數量確定了，就好辦了，我們直接枚舉所有三個數的組合，然後所有和等於0的組合就是答案。但是這裡有一個小問題，當我們找到了答案之後，我們並不能直接返回，因為數組當中重複的元素很有可能會導致答案的重複，我們必須要去掉這些重複的答案，保證答案當中每一個都是唯一的。

那我們先對原數組做處理，去除掉其中重複的元素之後再來尋找答案可不可以呢？

很遺憾，這個想法很好，但是不可行。原因也很簡單，因為答案不能重複，但是答案裡的數是可以重複的。

舉個例子，比如數組是[-1, -1, 2, 0, -2]，那麼[-1, -1, 2]是一個答案，如果一開始就出去掉了重複的-1，那麼這個答案顯然就無法構成了。唯一的解決方法是用容器來維護答案，保證容器內的答案是唯一的，不過這個會帶來額外的時間和空間開銷。

所以，總體看來，暴力枚舉並不是個好方法，複雜度不低，如果使用C++和Java等語言的話，使用容器也很麻煩。

ret = set()
for i in range(n):    for j in range(i+1, n):        for k in range(j+1, n):            if a[i] + a[j] + a[k] == 0:                ret.add((i, j, k))
return list(ret)

  利用2 Sum  

還有一個思路是利用之前的2 Sum的解法，在之前的2 Sum問題當中，我們通過巧妙地使用map，來達成了在複雜度內找到了所有和等於某個值的元素對。所以，我們可以先枚舉第一個數的大小，然後在剩下的元素當中進行2 Sum操作。

假設我們枚舉的數是a[i],那麼我們在剩下的元素當中做2 Sum，來尋找和等於-a[i]的兩個數。最後，將這三個數組成答案。如果遺忘2 Sum解法的同學可以點擊下方連結回到之前的文章。LeetCode 1 Two Sum——在數組上遍歷出花樣

這個方法看起來巧妙很多，但是還是逃不掉重複的問題。舉個例子：[-1, -1, -1, -1, -1, 2]。如果我們枚舉-1，那麼會出現多個[-1, -1, 2]的結果。所以我們依然免不了手動過濾重複的答案。不過利用2 Sum的解法要比暴力快一些，因為2 Sum的時間複雜度是，再乘上枚舉元素的複雜度，不考慮去重情況下的整體複雜度是O(n^2)，要比枚舉的O(n^3)更優。

我們利用2 sum寫出新的算法：

def two_sum(array, idx, target):    """    two sum的部分    """    n = len(array)    ret = []    # 用來記錄所有出現過的元素    appear = set()    # 用來判斷2 sum的答案出現重複    used = set()    for i in range(idx + 1, n):        # 如果 target - array[i]之前出現過，說明可以構成答案        if target - array[i] in appear:            # 判斷答案是否重複            if array[i] in used or target - array[i] in used:                continue            # 記錄            used.add(array[i])            used.add(target - array[i])            ret.append((array[i], target - array[i]))        appear.add(array[i])    return ret

def three_sum(array):    n = len(array)    # 記錄枚舉過的元素    used = set()    ret = []    # 防止答案重複    duplicated = set()    for i in range(n):        # 如果出現過，說明已經枚舉過，跳過        if array[i] in used:            continue        # 拿到2 sum的答案        combinations = two_sum(array, i, -array[i])        if len(combinations) > 0:            for combination in combinations:                # 組裝答案                answer = tuple(sorted((array[i], *combination)))                # 判斷答案是否重複                if answer in duplicated:                    continue                # 記錄                ret.append(answer)                duplicated.add(answer)        used.add(array[i])    return ret

  尺取法  

這題的另一個解法是尺取法，也就是two pointers，也叫做兩指針算法。這個在我們之前的文章當中也有過介紹，有遺忘或者錯過的同學可以點擊下方的連結回顧一下。LeetCode3 一題學會尺取算法

尺取法的精髓是通過兩個指針控制一個區間，保證區間滿足一定的條件。在這題當中，我們要控制的條件其實是三個數的和。由於我們的指針數量是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需要跳過所有重複的數字，避免重複。

我們寫出代碼：

def three_sum(array):    n = len(array)    # 先對array進行排序    array = sorted(array)    ret = []    for i in range(n-2):        # 判斷第一個數是否重複        if i > 0 and array[i] == array[i-1]:            continue        used.add(array[i])        # 進行two pointers縮放        j = i + 1        k = n - 1        target = -array[i]        if target < 0:            break        while j < k:            cur_sum = array[j] + array[k]            # 判斷當前區間的結果和目標的大小            if cur_sum < target:                    j += 1                continue            elif cur_sum > target:                k -= 1                continue            # 記錄            ret.append(answer)            # 繼續縮放區間，尋找其他可能的答案            j += 1            while j < k and array[j] == array[j-1]:                j += 1            k -= 1            while j < k-1 and array[k] == array[k+1]:                k -= 1    return ret


寫出代碼之後，我們來分析一下算法的複雜度。一開始的時候，我們對數組進行排序，眾所周知，排序的複雜度是。之後，我們枚舉了第一個數，開銷是，我們進行區間縮放的複雜度也是，所以整個主體程序的複雜度是。看似和上面一種方法區別不大，但是我們節省了set重複的判斷，由於hashset讀取會有時間開銷，所以雖然算法的量級上沒什麼差別，但是常數更小，真正運行起來這種算法要快很多。

這題官方給的難度是Medium，但實際上我覺得比一般的Medium要難上一些，代碼量也要大上一些。今天文章當中列舉的並不是全部的解法，其他的做法還有很多，比如對所有數進行分類，分成負數、零和正數，然後再進行組裝等等。感興趣的同學可以自己思考，看看還有沒有其他比較有趣的方法。

今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。