題目

  • 題目連結
  • 目標函式 : threeSum(nums)
    • Input : nums: List[int]
    • Output : List[List[int]]

解題概念

  • 題意 : 給定一整數陣列 nums，需要回傳所有 [nums[i], nums[j], nums[k]] 的組合，其中
    1. i != j、i != k 且 j != k
    2. nums[i ] + nums[j] + nums[k] == 0
    3. Solution 中不得包含重複之組合

我的寫法

  • 想法 :
    • 使用 Bubble Sort 的兩兩搜尋方式
    • 在雙重迴圈中需要去判斷 :
      1. 陣列 temp 去紀錄 nums 移除掉 nums[i] 與 nums[j] 的元素
      2. 若 -(nums[i] + nums[j]) 存在於 temp 中，代表有一組合成立，便將 [nums[i], nums[j], -(nums[i] + nums[j])] 加入 res 中
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    def threeSum(self, nums):
        
        res = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                temp = [n for n in nums if n != i and n != j]
                if -(nums[i] + nums[j]) in temp:
                    res.append([nums[i], nums[j], -(nums[i] + nums[j])])
        return res
  • 成效 :
    • Time Complexity : $O(n^3)$
    • Result : Wrong Answer
    • 原因 : 沒有把重複之組合排除掉

解答 or 其他優秀寫法

  • 想法 : 在改變三個指標位置的過程中，要注意保持
    1. left $\lt$ mid $\lt$ right
    2. nums[left] $\le$ nums[mid] $\le$ nums[right]
  • 實作過程 :
    1. 先將 nums 排序過一次
    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
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    def threeSum(self, nums):
        
        nums.sort()
        result = []

        # 讓 mid、right可以保持在 len(nums) 中
        for left in range(len(nums) - 2): 
            
            # 若 nums[left] > 0，代表此時三個加總一定會超過0，因此此回合就沒有比較的必要
            if nums[left] > 0 : break 
            
            # 若發現 nums[left] 跟上一回合一樣，則跳過此回合 (以避免重複組合)
            if left > 0 and nums[left] == nums[left - 1]: 
                continue

            # 將 mid 設為 left 右邊的元素
            mid = left + 1

            # 將 right 設為 left 右邊的元素
            right = len(nums) - 1

            # 然後 mid 向右、right 向左雙向搜尋
            while mid < right:

                # 若 nums[right] < 0，代表此時三個加總一定會小於0，因此此回合就沒有比較的必要
                if nums[right] < 0 : break

                curr_sum = nums[left] + nums[mid] + nums[right] # 計算此回合的加總值
                
                # 若 curr_sum < 0，代表需要更多的正數，但 nums[right] 無法再變大，因此需要將 mid 右移
                if curr_sum < 0:
                    mid += 1 

                # 若 curr_sum > 0，代表需要更多的負數，但 nums[mid] 無法再變小，因此需要將 left 左移
                elif curr_sum > 0:
                    right -= 1

                # 若 curr_sum == 0，代表該組合是我們要的
                else:
                    result.append([nums[left], nums[mid], nums[right]]) # 將組合儲存下來

                    # 若發現 mid 與右側的元素相同，則將 mid 右移，以避免重複組合
                    while mid < right and nums[mid] == nums[mid + 1] : 
                        mid += 1

                    # 若發現 right 與左側的元素相同，則將 right 左移，以避免重複組合
                    while mid < right and nums[right] == nums[right - 1] : 
                        right -= 1

                    # 最後各自再移動一次，以比較新的兩個元素
                    mid += 1
                    right -= 1
        return result
  • 成效 :
    • Time Complexity : $O(n^2)$
    • Runtime: 769 ms (faster than 81.31%)
    • Memory Usage: 16.70 MB (more than 40.88%)