LeetCode 筆記 - 18. 4Sum

題目在此 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

也許你也會想看看