[LeetCode解題攻略] 15. 3Sum

題目描述

給定整數陣列nums，傳回所有三元組[nums[i], nums[j], nums[k]]，使得i != j, i != k, j != k，且nums[i ] + nums[j] + nums[k] == 0。

請注意，解決方案集不得包含重複的三元組。

1. 範例 1：

   Input: nums = [-1, 0, 1, 2, -1, -4]
   Output: [[-1, -1, 2], [-1, 0, 1]]

2. • 和為 0 的三元組為 [-1, -1, 2] 和 [-1, 0, 1]。
2. 範例 2：

   Input: nums = [0, 1, 1]
   Output: []

3. • 唯一可能的三元組和不等於 0。
3. 範例 3：

   Input: nums = [0, 0, 0]
   Output: [0, 0, 0]

4. • 唯一可能的三元組之和為 0。

解題思路

這題的核心是如何高效地找到所有符合條件的三元組，同時避免重複。以下是常見的解法：

1. 暴力解法：使用三層迴圈遍歷所有三元組並檢查和是否為零。
2. 排序 + 雙指針：利用排序後的性質，將問題轉換為類似 Two Sum 的雙指針解法。
3. HashSet 儲存結果：用雜湊結構儲存已發現的三元組以去除重複的結果。

解法 1：暴力解法

思路

直接使用三層迴圈枚舉所有三元組，檢查每組數字的和是否為零。如果成立，將該三元組加入結果集。

實現 (Python)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplet = sorted([nums[i], nums[j], nums[k]])
                        if triplet not in result:
                            result.append(triplet)

        return result

時間與空間複雜度

• 時間複雜度：O(n³)，三層迴圈遍歷所有可能組合。
• 空間複雜度：O(n)，結果集中最多存儲所有三元組。

解法 2：排序 + 雙指針

思路

1. 排序：先對數組進行升序排序，這樣可以有效避免重複並簡化搜索範圍。
2. 固定一個數字，轉換為 Two Sum：遍歷每個數字作為固定的第一個數字，然後在剩下的數組中使用雙指針找到和為目標值（即 -固定數字）的兩個數。
3. 跳過重複數字：為了避免重複，對固定數字和雙指針進行去重處理。

實現 (Python)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()  # 排序
        result = []
        n = len(nums)

        for i in range(n):
            # 避免固定數字重複
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            target = -nums[i]  # 尋找和為 -nums[i] 的兩數
            left, right = i + 1, n - 1

            while left < right:
                current_sum = nums[left] + nums[right]
                if current_sum == target:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    # 跳過重複數字
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif current_sum < target:
                    left += 1  # 當前和小於目標，移動左指針
                else:
                    right -= 1  # 當前和大於目標，移動右指針

        return result

時間與空間複雜度

• 時間複雜度：O(n²)
• • 排序的時間複雜度為 O(n log n)，雙指針部分為 O(n²)，所以總計 O(n²)。
• 空間複雜度：O(1)
• • 除了返回結果外，僅需額外變數儲存指針與目標值。

解法 3：HashSet 儲存結果

思路

1. 使用兩層迴圈，對於每個固定數字，將問題轉換為 Two Sum。
2. 用 HashSet 儲存已訪問過的數字，並檢查是否存在補數。
3. 用另一個 HashSet 儲存已找到的三元組，以去除重複結果。

實現 (Python)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = set()  # 使用 set 去除重複結果
        n = len(nums)

        for i in range(n):
            target = -nums[i]
            seen = set()  # 儲存當前已訪問的數字
            for j in range(i + 1, n):
                complement = target - nums[j]
                if complement in seen:
                    result.add((nums[i], nums[j], complement))
                seen.add(nums[j])

        return [list(triplet) for triplet in result]

時間與空間複雜度

• 時間複雜度：O(n²)
• • 外層迴圈為 O(n)，內層使用 HashSet 檢查補數的操作為 O(n)，總計 O(n²)。
• 空間複雜度：O(n)
• • 使用了額外的 HashSet 儲存已訪問的數字。

總結

最推薦的解法是 排序 + 雙指針法，因為它的時間複雜度較低，且能在不額外消耗太多空間的情況下解決問題。如果希望更靈活地處理重複三元組，則可以選擇 HashSet 儲存結果 的方法。