今天挑戰的是經典題目 3Sum。這題幾乎每個刷 LeetCode 的人都會遇到，因為它涵蓋了排序、雙指針，以及如何去除重複解的技巧。

題目核心

我們要從陣列裡找出所有 三個數字加起來等於 0 的組合，並且結果裡不能有重複的三元組。

範例：

[-1,0,1,2,-1,-4] → [[-1,-1,2], [-1,0,1]]

[0,1,1] → []

[0,0,0] → [[0,0,0]]

解題思路

排序：
先把陣列排序，這樣方便我們用雙指針移動。

固定一個數字，雙指針找另外兩個：
假設固定 nums[i]，那我們就要找 [i+1, end] 之間兩個數字，讓它們的和等於 -nums[i]。

避免重複：

外層迴圈：若 nums[i] == nums[i-1]，就跳過。

內層雙指針：找到一組解後，左右指針要跳過重複的數字。

Java 程式碼
import java.util.*;

class Solution {
public List<List> threeSum(int[] nums) {
List<List> res = new ArrayList<>();
Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        // 跳過重複的 i
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // 跳過重複的 left/right
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

}

心得

這題算是「雙指針」的進階版。
一開始如果用三層迴圈，時間複雜度會到 O(n^3)，完全會 TLE。
而利用排序 + 雙指針，時間就降到 O(n^2)，這樣在 n <= 3000 的情況下就能過。

最麻煩的就是 去重複，不管是外層還是內層指針，都要小心跳過相同數字，否則答案會多一堆重複組合。