18. 4Sum

發表於 分類於 ， 閱讀次數： 文章字數： 1.6k

種類 : two pointers, hash table
難度 : medium
題目 : 18. 4Sum

思維邏輯

  1. 與暴力解法相似，僅在最後一個迴圈使用dict優化

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
dict
"""
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]: 
        freq = dict()
        for num in nums:
            freq[num] = freq.get(num, 0) + 1

        res = set()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    temp = target - nums[i] - nums[j] - nums[k]
                    if temp in freq:
                        count = (nums[i] == temp) + (nums[j] == temp) + (nums[k] == temp)
                        if freq[temp] > count:
                            res.add(tuple(sorted([nums[i], nums[j], nums[k], temp])))
        return list(res)

時間複雜度: O(n3)
空間複雜度: O(n)

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
43
44
45
46
47
48
49
50
51
52
"""
two pointers
"""
class Solution:
    def fourSum(self, nums:list, target:int): 
        # 0. 排序
        # 1. 兩層迴圈，固定前兩個元素
        # 2. two pointer 解target - 兩元素相加
        
        nums.sort()
        res = []
        for i in range(len(nums)):
            # 剪枝[可略]: 元素>target and 後面元素均>0
            if nums[i] > target and nums[i] > 0:
                break

            # 去重
            if i > 0 and nums[i] == nums[i-1]:
                continue

            for j in range(i+1, len(nums)):
                # 剪枝[可略]: 元素相加>target and 後面元素均>0
                if nums[i] + nums[j] < target and nums[j] > 0:
                    break

                # 去重
                if j > i+1 and nums[j] == nums[j-1]:
                    continue

                # two sum(sub_target)
                left, right = j+1, len(nums)-1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if target == s:
                        res.append([nums[i], nums[j], nums[left], nums[right]])

                        # 去重(left)
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        # 去重(right)
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1

                        # 已加入list
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1
        
        return res

時間複雜度: O(n3)
空間複雜度: O(1)

難點

  1. 與15. 3Sum相似，四個元素不重複，但輸出時需過濾掉重複值
  2. 無排序(有排序使用雙指針較有效率)
  3. 雙指針去重(優化迴圈)
  4. 雙指針剪枝(優化迴圈)

最佳解法

此為最佳解法