LeetCode 筆記 - 15. 3Sum

Posted on 標籤
探討經典的 3Sum 問題。本文解析如何將三數之和降維思考為多次的 Two Sum，將複雜度從 O(N^3) 優化至 O(N^2)。文中介紹兩種主流演算法策略，協助讀者在面對海量數列時，依然能高效找出總和為零的所有組合。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 15. 3Sum

給定一個數列，請找出 3 個數字相加等於 0 的組合

解題思維

這題如果單純暴力解，只會寫出 $O(N^3)$ 的演算法
但在這裡我們不做那種事

首先我們可以把問題降維思考為，選一個數字然後做 Two Sum
也就是說只要做 n 次 Two Sum 就可以掃瞄完畢了

所以關鍵在於說如何有效率的做 Two Sum
在這裡有兩種演算法，兩種在 Two Sum 都可以拿到好成績
但在這題因為會重複的一直做，而有明顯的差別

  1. 使用 Map 加速搜尋
    缺點是 Map 使用了大量的 Hash 計算，還會消耗 $O(n)$ 的空間
  2. 使用 Two Pointers 大法
    Two Pointers 大法的前提是會需要先 Sorting，雖然一開始使用了 Sorting 會消耗 $O(n \log n)$
    但 Sorting 過後有一些加速技巧可以使用，所以在這題的測資上，效果反而比較好

所以在實作上，筆者用了 Two Pointers 大法，來實作 Two Sum
再加上一些加速的小技巧，來跳過重複的組合

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        if (size := len(nums)) == 3:
            if sum(nums) == 0:
                return [nums]
            return []

        result = set()
        
        nums.sort()

        last_num = None
        for i in range(size - 2):
            if nums[i] == last_num:
                continue
            last_num = nums[i]
    
            target = -nums[i]

            left = i + 1
            right = size - 1

            while left < right:

                n = nums[left] + nums[right]

                if n == target:
                    r = (nums[i], nums[left], nums[right])

                    result.add(r)
                    
                    left += 1
                    right -= 1
                elif n < target:
                    left += 1
                else:
                    right -= 1

        return result

也許你也會想看看