題目在此 18. 4Sum
給一個數列跟一個 target，請從數列找出 4 個數相加等於 target
解題思維
在這裡千萬千萬不要寫成 O(N4)，這麼明顯的魔鬼陷阱不要跳進去啊各位同學
基本概念是兩兩組合出，各種組合的可能存成 dict，O(N2) 就可以做完了
接著再使用一次兩兩組合，看看需要的值有沒有在 dict 裡
有一個加速小技巧是先把數列 Sorting 後，可以跳過一些重複的計算
總共還是在 O(N2) 的範圍內
完成 🙂
程式碼
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
41
42
| class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if (length := len(nums)) < 4:
return []
nums.sort()
value_map = collections.defaultdict(set)
for flag_0 in range(length):
if flag_0 > 0 and nums[flag_0] == nums[flag_0 - 1]:
continue
for flag_1 in range(flag_0 + 1, length):
if flag_1 > 0 and nums[flag_1] == nums[flag_1 - 1] and flag_0 < flag_1 - 1:
continue
value = nums[flag_0] + nums[flag_1]
value_map[value].add((flag_0, flag_1))
result = []
for flag_0 in range(length):
for flag_1 in range(flag_0 + 1, length):
if flag_1 > 0 and nums[flag_1] == nums[flag_1 - 1] and flag_0 < flag_1 - 1:
continue
value = nums[flag_0] + nums[flag_1]
if (check_value := target - value) in value_map:
for f_0, f_1 in value_map[check_value]:
candidate_list = [f_0, f_1]
if flag_0 in candidate_list or flag_1 in candidate_list:
continue
value_list = sorted([nums[i] for i in [flag_0, flag_1] + candidate_list])
if value_list not in result:
result.append(value_list)
return result
|
相關文章