15. 3Sum

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

種類 : two pointers, hash table
難度 : medium
題目 : 15. 3Sum

思維邏輯

  1. 區分正、負、零組合
    1. 篩選至list，區分正數、負數、零
    2. 建立正負set
    3. 若有0，檢核正負是否有對應值
    4. 檢核是否有[0, 0, 0]
    5. 負數任2組合，檢核正數set是否相符
    6. 正數任2組合，檢核負數set是否相符

解法

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
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        # 0.init
        res = set()
        p, n, z = [], [], []

        # 1. filter nums to p, n, z
        for num in nums:
            if num > 0:
                p.append(num)
            elif num < 0:
                n.append(num)
            else:
                z.append(num)

        # 2. create N, P set
        N, P = set(n), set(p)

        # 3. 若有z, 檢核N, P是否符合
        if z:
            for num in N:
                if num*-1 in P:
                    res.add((num, 0, num*-1))
        
        # 4. 若有[0, 0, 0]
        if len(z) >= 3:
            res.add((0, 0, 0))

        # 5. 任2負數，P是否相符
        for i in range(len(n)):
            for j in range(i+1, len(n)):
                target = (n[i] + n[j]) * -1
                if target in P:
                    res.add(
                        tuple(
                            sorted(
                                [n[i], n[j], target]
                                )))

        # 6. 任2正數，N是否相符
        for i in range(len(p)):
            for j in range(i+1, len(p)):
                target = (p[i] + p[j]) * -1
                if target in N:
                    res.add(tuple(sorted([p[i], p[j], target])))

        return list(res)

時間複雜度: O(n+2n2) -> O(n2)
空間複雜度: O(2n)

難點

  1. 三個元素不重複，但輸出時需過濾掉重複值
  2. 無排序(有排序使用雙指針較有效率)

最佳解法

此為最佳解法

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
"""
雙指針
使用前需先排序
"""
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        
        for i in range(len(nums)):
            # 如果第一个元素已经大于0，不需要进一步检查
            if nums[i] > 0:
                return result
            
            # 跳过相同的元素以避免重复
            if i > 0 and nums[i] == nums[i - 1]:
                continue
                
            left = i + 1
            right = len(nums) - 1
            
            while right > left:
                sum_ = nums[i] + nums[left] + nums[right]
                
                if sum_ < 0:
                    left += 1
                elif sum_ > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # 跳过相同的元素以避免重复
                    while right > left and nums[right] == nums[right - 1]:
                        right -= 1
                    while right > left and nums[left] == nums[left + 1]:
                        left += 1
                        
                    right -= 1
                    left += 1
                    
        return result

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