題目在此 15. 3Sum
給定一個數列，請找出 3 個數字相加等於 0 的組合
解題思維
這題如果單純暴力解，只會寫出 $O(N^3)$ 的演算法
但在這裡我們不做那種事
首先我們可以把問題降維思考為，選一個數字然後做 Two Sum
也就是說只要做 n 次 Two Sum 就可以掃瞄完畢了
所以關鍵在於說如何有效率的做 Two Sum
在這裡有兩種演算法，兩種在 Two Sum 都可以拿到好成績
但在這題因為會重複的一直做，而有明顯的差別
- 使用 Map 加速搜尋
缺點是 Map 使用了大量的 Hash 計算，還會消耗 $O(n)$ 的空間 - 使用 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
|
也許你也會想看看