LeetCode 筆記 - 15. 3Sum

Posted on

題目在此 15. 3Sum

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

解題思維

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

首先我們可以把問題降維思考為，選一個數字然後做 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

相關文章