LeetCode 獨自升級紀 - [Two Pointer] 3sum (Medium)

# 題目

給定一個整數數組 nums，判斷是否存在三個元素 a，b，c，使得 a + b + c = 0？找出所有滿足條件且不重複的三元組。

# Two Pointer

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:  # type: ignore
        result = []
        nums.sort()  # 先排序，方便後續處理

        for i, a in enumerate(nums):

            if a > 0:  # 如果 a > 0，後面都不可能有三個數字加起來等於 0
                break

            if (
                i > 0 and a == nums[i - 1]
            ):  #  跳過重複的「起始值」a，i > 0 是防止出現 nums[0] 跟 nums[-1] 比較，導致比較第一個跟最後一個元素的情況
                # a == nums[i - 1] 是避免 不同 index 但 value 一樣 的情況 ex: [-1,-1,...]
                continue

            l, r = i + 1, len(nums) - 1  # 左右指針
            while l < r:
                total = a + nums[l] + nums[r]
                if total > 0:  # 因為是 sorted 的，代表 nums[r] 太大了
                    r -= 1
                elif total < 0:
                    l += 1
                else:
                    result.append([a, nums[l], nums[r]])
                    # [-2,-2,0,0,2,2]
                    l += 1
                    # 跳過重複的 left pointer 值
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1

        return result

• TC：O(n^2)
• SC：O(n)

為何一開始要

if a > 0:
    break

因為 nums 是 sorted 的，所以如果當前的 a 已經大於 0，後面的數字只會更大，就不可能再找到符合條件的組合，例如：

nums = [-4, -1, -1, 0, 1, 2]

• 當 a = -4 或 -1，還可能湊出 0
• 當 a = 0，還可能有 [0,0,0]
• 但當 a = 1 的時候，因為後面全是 1, 2, ...
  • 最小的總和是 1 + 1 + 2 = 4 > 0。沒必要再檢查，直接結束迴圈

還有為何除了比較下一個值是否與前一個值相同外 a == nums[i - 1]，還要比較 i > 0 ？

nums = [0,0,0]
nums.sort()
result = []

for i, a in enumerate(nums):
    if nums[i] == nums[i-1]:   # ❌ 沒有 i>0 保護
        continue

    l, r = i+1, len(nums)-1
    while l < r:
        total = a + nums[l] + nums[r]
        if total == 0:
            result.append([a, nums[l], nums[r]])
            l += 1
            r -= 1

print(result)

假設 i 為 0，則 nums[i - 1] 會變成 nums[-1]，這樣就會比較當第一個元素與最後一個元素

執行流程

1. i = 0

   • 判斷：nums[0] == nums[-1] → 0 == 0 → 成立！
   • 所以直接 continue 跳過，連雙指針都沒跑。
   • 第一個合法的 0 被整個跳掉了。

2. i = 1

   • 判斷：nums[1] == nums[0] → 0 == 0 → 成立，再跳過。

3. i = 2

   • 判斷：nums[2] == nums[1] → 0 == 0 → 成立，再跳過。

結果變成 result = []，沒找到解，但其實 [0,0,0] 是正解。

# Brute Force

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        results = set()  # 用 set 避免重複

        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:
                        three_num = tuple(sorted([nums[i], nums[j], nums[k]])) # set 內的元素必須要是能 Hashable的
                        results.add(three_num)

        # set 轉回 list[list]
        return [list(t) for t in results]

• TC：O(n^3)
• SC：O(m)