LeetCode 15. 3Sum 三數之和——高效去重解法

LeetCode 15. 3Sum 三數之和——高效去重解法

給定包含 n 個整數的數組 S，找出所有不重複的三元組 (a, b, c)，使得 a + b + c = 0。要求三元組內元素非遞減（a ≤ b ≤ c），結果集不含重複三元組。

暴力解法的缺陷

原代碼使用三層循環配合 HashMap 去重，時間複雜度 O(n³)，極易超時。且 List 作為 Map 鍵值時，containsKey 比較的是引用而非內容，去重失效。

優化方案：排序 + 雙指針

1. 先對數組排序，便於去重與剪枝；
2. 固定第一個數 nums[i]，在剩餘區間 [i+1, n-1] 使用雙指針 L、R 尋找 nums[L] + nums[R] = -nums[i]；
3. 跳過重複元素：i > 0 && nums[i] == nums[i-1] 直接 continue；同理移動 L、R 時跳過相鄰重複值。

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

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
        if (nums[i] > 0) break; // 剪枝：最小值已 > 0

        int target = -nums[i];
        int L = i + 1, R = n - 1;
        while (L < R) {
            int sum = nums[L] + nums[R];
            if (sum == target) {
                res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                while (L < R && nums[L] == nums[L + 1]) L++; // 去重
                while (L < R && nums[R] == nums[R - 1]) R--;
                L++; R--;
            } else if (sum < target) {
                L++;
            } else {
                R--;
            }
        }
    }
    return res;
}

時間複雜度 O(n²)，空間複雜度 O(1)（不計結果集），完美通過測試用例。