【Leetcode 筆記】 15. 3Sum

題目解釋

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

i != j, i != k, and j != k，且 solution 內不得包含重複的三元組 (tripet)。

範例

• 輸入: nums = [-1, 0, 1, 2, -1, -4]
• 輸出: [[-1, -1, 2],[-1, 0, 1]]

[-1, -1, 2] 與 [-1, 0, 1] 這兩種 tripet 都可以使其和為 0。

最佳解法 (Follow-up)

先將 nums 排序過會省很多時間，因為我們就可以按照相加總和的數值大小來判定我們雙指標要怎麼走。

3Sum 可以拆解為 1 num + 2 num 的形式，所以我們令一迴圈固定某數字做為 anchor，剩下兩個數字就由雙指標決定。

假設我們現在有一 array :

[  -4,     -1,    -1, 0, 1,    2]
(Anchor)  (left)            (right)

curr_sum = nums[Anchor] + nums[left] + nums[right]

步驟

1. 先將 nums 排序一下
2. 令一迴圈，想像 i 作為不動的 anchor，其餘部分交給雙指標 left 跟 right 來掃
3. 比較 anchor + nums[left] + nums[right] 的總和
   • if 總和 == 0，讚讚，加進我們要回傳的 res 裡面
   • if 總和 > 0，代表 nums[right] 太大，right 縮回來一格
   • if 總和 < 0，代表 nums[left] 太小，left 前進一格
4. 回傳 res

所以程式碼長的像這樣：
( 注意外面迴圈是到 len(nums) - 2 而已，因為我們要三個元素相加 )

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i in range(len(nums) - 2):
            anchor = nums[i]
            left, right = i + 1, len(nums) - 1

            while left < right:
                curr_sum = anchor + nums[left] + nums[right]
                if curr_sum == 0:
                    res.append([anchor, nums[left], nums[right]])
                    left += 1
                    right -= 1
                elif curr_sum > 0:
                    right -= 1
                else:
                    left += 1

        return res

打完收工！
…
咦？怎麼出錯了 QQ

注意 ⚠️

沒錯，我們還沒處理遇到兩個一樣 element 的情況，以這 test case 而言會長的像這樣。

[  0,       0,       0,         0]
(Anchor)  (left)             (right)
=> 此時 append 一次 [0, 0, 0]
[  0,       0,       0,         0]
         (Anchor)  (left)    (right)
=> 又被 append 一次 [0, 0, 0] 了 😡 ！！！

所以我們必須加上能夠防範的機制，既然 set 不能擋長一樣的 list，只好從源頭開始擋。

對於 i 的重複值防範

if (i > 0) and (nums[i] == nums[i - 1]):
    continue

我們確認 nums[i] 跟 nums[i - 1] 是否一致，如果一樣的話就跳過此次迴圈，i > 0 是防止 index error。

對於 left 的重複值防範

if (left < right) and (nums[left] == nums[left - 1]):
    left += 1

外圈的 i 已經被防範了，所以內圈的也要如法炮製。

對於 right 的重複值防範

if (left < right) and (nums[right] == nums[right + 1]):
    right += 1

如法炮製。

程式碼

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i in range(len(nums) - 2):
            if (i > 0) and (nums[i] == nums[i -1]):
                continue
            else:
                anchor = nums[i]
                left, right = i + 1, len(nums) - 1

                while left < right:
                    curr_sum = anchor + nums[left] + nums[right]

                    if curr_sum == 0:
                        res.append([anchor, 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 curr_sum > 0:
                        right -= 1
                    else:
                        left += 1

        return res

偷懶解法

把 res 改成 set 並 add tuple 進去，
這樣就可以自己去 duplicate 的 tripets 了👍

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = set()

        for i in range(len(nums) - 2):
            anchor = nums[i]
            left, right = i + 1, len(nums) - 1

            while left < right:
                curr_sum = anchor + nums[left] + nums[right]
                if curr_sum > 0:
                    right -= 1
                elif curr_sum < 0:
                    left += 1
                else:
                    res.add((anchor, nums[left], nums[right]))
                    left += 1
                    right -= 1
        return res

時間複雜度

O(n^2)，n 是 num 的元素個數，用了雙層迴圈。

空間複雜度

O(n)。

結語

Two Sum 跟 3Sum 之間的距離 be like:

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26