LeetCode15題：尋找三數和，附完整程式碼

2020 年 3 月 5 日
筆記

點擊上方藍字，和我一起學技術。

Link

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

Difficulty

Medium

描述

給定一個整數的數組，要求尋找當中所有的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.

樣例

題解

這道題是之前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要難上一些，程式碼量也要大上一些。今天文章當中列舉的並不是全部的解法，其他的做法還有很多，比如對所有數進行分類，分成負數、零和正數，然後再進行組裝等等。感興趣的同學可以自己思考，看看還有沒有其他比較有趣的方法。

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