LeetCode 15. 3Sum：排序 + 雙指針 + 去重模板完整解析

題目重述

給定整數數組 nums，找出所有 **不重複** 的三元組 [a, b, c] 使 a + b + c = 0。
要求：a ≤ b ≤ c，結果集無重複三元組。

核心思路：排序 + 固定一邊 + 雙指針

1. 排序數組 O(n log n)。
2. 枚舉第一個數 nums[i] (i = 0..n-3)。
3. 在 i+1 .. n-1 區間雙指針 L, R 尋找 nums[L] + nums[R] = -nums[i]。
4. **去重關鍵**：
   • 外層：if (i > 0 && nums[i] == nums[i-1]) continue;
   • 內層找到解後：while (L < R && nums[L] == nums[L+1]) ++L; 同理 R。

完整 Java 代碼

class Solution {
    public List> threeSum(int[] nums) {
        List> res = new ArrayList<>();
        if (nums.length < 3) return res;

        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳過重複首元素
            int target = -nums[i];
            int L = i + 1, R = nums.length - 1;
            while (L < R) {
                int sum = nums[L] + nums[R];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    ++L; --R;
                    while (L < R && nums[L] == nums[L - 1]) ++L; // 去重 L
                    while (L < R && nums[R] == nums[R + 1]) --R; // 去重 R
                } else if (sum < target) {
                    ++L;
                } else {
                    --R;
                }
            }
        }
        return res;
    }
}

複雜度分析

• 時間：O(n^2) —— 排序 O(n log n) + 雙層循環 O(n^2)。
• 空間：O(1) (不計輸出) / O(k) (輸出列表)。

去重邏輯圖解

nums = [-4, -1, -1, 0, 1, 2]
i=0 (-4)  target=4  L=1 R=5  sum=1  L++
i=1 (-1)  target=1  L=2 R=5  sum=1  ✓ [-1,-1,2]  L=3 R=4  sum=1  ✓ [-1,0,1]  L=4 R=3 stop
i=2 (-1)  skip (nums[2]==nums[1])
i=3 (0)   target=0  L=4 R=5  sum=3  R--
...
結果：[[-1,-1,2], [-1,0,1]]

常見變體與優化

避坑清單

1. 外層去重條件：i > 0 而非 i >= 0，首元素不跳過。
2. 內層去重時機：**找到解後** 移動指針再去重，否則會漏解。
3. 長整型溢出：nums[i] + nums[L] + nums[R] 可能超 int，用 long 或先比較 nums[L] + nums[R] 與 -nums[i]。
4. 數組長度 < 3：直接返回空列表。

總結

3Sum 是 **雙指針去重模板** 的經典入門。
掌握三步曲：排序 → 固定一邊 → 雙指針收斂 + 兩層去重，即可舉一反三解決 k-Sum 系列問題。
生活感悟：代碼寫完別忘陪伴家人，財務自由的終點是有時間愛人。

1. 上一篇文章： Acdream OJ 1116：字符串 Hash + 二分 + 矩陣快速冪求斐波那契加權和
2. 下一篇文章： HDU 1717 小數化分數 2：循環小數轉分數完整算法與代碼

C++ 入門

S3C2416 睡眠喚醒流程詳解：從啟用喚醒源到內核識別中斷

睡眠恢復流程（s3c_pm_enter 後半部） stati

設計模式 C++ 實戰（14）：外觀模式 —— 為複雜子系統提供統一高層接口

外觀模式是結構型模式中最實用、應用最廣的模式之一。它為子系統

C++ D&A 5 實戰：基於虛繼承的 Collection 框架實現詳解

項目背景 實現一個基於繼承體系的容器框架，核心類包括抽象基類

LeetCode N-Queens II：N 皇后問題計數

LeetCode N-Queens II 題目描述 在 N