LeetCode - 3Sum（三數之和）

題目描述

給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a、b、c 使得 a + b + c = 0。找出所有滿足條件且不重複的三元組 a, b, c。答案中每個三元組需按非降序排列，且答案集中不能包含重複的三元組。

範例：

輸入：nums = [-1, 0, 1, 2, -1, -4]
輸出：[[-1, -1, 2], [-1, 0, 1]]
解釋：nums 中滿足 a + b + c = 0 的三元組有 [-1, -1, 2] 和 [-1, 0, 1]

注意：

• 不能包含重複的三元組，順序無關。
• 若找不到符合條件的三元組，返回空列表。

解法思路

1. 排序數組：將 nums 排序，方便後續去重並使用雙指針法。
2. 遍歷數組：固定一個數作為 a，然後在其右側區域使用雙指針找到和為 -a 的兩個數 b 和 c。
3. 雙指針查找：
   • 對於固定的 a，設兩個指針 left 和 right 在 a 的右側部分，分別指向頭尾。
   • 若 nums[left] + nums[right] + a == 0，則找到一組解並加入結果中，然後移動指針以繼續尋找。
   • 若和小於 0，移動 left 指針以增加總和；若和大於 0，移動 right 指針以減少總和。
4. 去重：為了避免重複的三元組，當 a、left、right 的值與上次相同時，跳過這些重複值。

範例代碼

以下是 Python 的實現：

def threeSum(nums):
    nums.sort()  # 排序數組
    result = []

    for i in range(len(nums) - 2):
        # 跳過重複的數字
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                # 移動指針並跳過重複的元素
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

代碼解析

1. 排序：先對 nums 排序，方便處理重複元素和使用雙指針。
2. 雙指針法：固定一個數 nums[i]，並使用雙指針在其右側部分找到和為 0 的三元組。
3. 去重：在每次加入結果和移動指針時，跳過重複元素，以避免結果中出現重複的三元組。

時間和空間複雜度

• 時間複雜度：O(N^2)，其中 N 是 nums 的長度。排序需要 O(N log N)，且雙指針遍歷為 O(N^2)。
• 空間複雜度：O(N)，主要用於排序和存儲結果。