3Sum 算法優化：從 O(n³) 暴力到 O(n²) 哈希索引，附去重邏輯與邊界處理

public List> threeSum(int[] nums) {
    Arrays.sort(nums);
    List> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue; // 跳過重複首元素
        if (nums[i] > 0) break; // 排序後首元素>0，後續全>0，不可能和為0
        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]));
                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)（不計輸出），代碼簡潔，業界標準解法。

第三層：哈希索引優化查找（本文原始思路）

構建 HashMap> 記錄每個值的所有下標（已排序）。固定 i,j 計算 need = -(nums[i]+nums[j])，查 Map 中是否存在 need 且下標 > j。去重用 Set 記錄 "a#b"。雖同為 O(n²)，但常數因子大、代碼複雜，**不推薦生產使用**，僅作為思維拓展。

關鍵優化點總結

擴展變體

• 3Sum Closest：找和最接近 target 的三元組，雙指針更新最小差值。
• 4Sum：固定兩層循環 + 雙指針，O(n³)。
• 3Sum Smaller：計數和小於 target 的三元組數，雙指針 count += R-L。