2025年12月7日

3Sum的双层去重

外层去重管"别问同一个问题两次"

内层去重管"回答同一个问题时别把同一个答案说两遍"。

位置	防的是什么重复	触发时机
外层（`i` 循环）	`nums[i]` 和上一个 `i` 值相同 → 两次调用在解完全相同的子问题，整个 twoSum 会被重跑一遍	每次进入新的 `i` 之前检查
内层（双指针内部）	同一次 twoSum 调用中，双指针换了下标但夹出的值组合相同 → 同一个答案被记两次	只在找到一个解之后才需要跳，跳的是"刚用过的值"

踩坑提醒：

内层去重必须放在"找到解、移动指针之后"，而不是在 sum < target / sum > target 的分支里——那些分支不产生答案，不存在"重复答案"的问题，加了去重反而会跳过合法的候选值。
外层去重解决不了内层重复（子数组内部值重复），内层去重也解决不了外层重复（相同的起点被重复问）——两层必须同时写，各管各的。
判断顺序是 nums[x] == nums[x-1]（跟前一个比），不是 nums[x] == nums[x+1]，方向搞反会导致漏判或数组越界。

剪枝（可选，优化实际运行速度，不改变最坏复杂度）

if (nums[i] > 0) break;（排序后，正数打头不可能凑出 0）
nums[i] + 最小两数 > 0 → 直接 break
nums[i] + 最大两数 < 0 → 直接 continue

复杂度

时间：O(n²)（排序 O(n log n) + 外层 O(n) × 内层 O(n)）
空间：O(1) 额外空间（不算结果集）

完整代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break; // If nums[i] > 0, nums[i + k] will > 0
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            twoSum(nums, i, res);
        }
        return res;
    }
 
    private void twoSum(int[] nums, int idx, List<List<Integer>> res) {
        int target = 0 - nums[idx];
        int start = idx + 1;
        int end = nums.length - 1;
        if (nums[idx] + nums[start] + nums[start + 1] > 0) return; // wil not get number smaller than nums[start + 1]
        if (nums[idx] + nums[end] + nums[end - 1] < 0) return; // wil not get number bigger than nums[end - 1]
        while (start < end) {
            if (nums[start] + nums[end] == target) {
                res.add(new ArrayList<>(Arrays.asList(nums[idx], nums[start], nums[end])));
                start++;
                end--;
                while (start < end && nums[start] == nums[start - 1]) {
                    start++;
                }
                while (start < end && nums[end] == nums[end + 1]) {
                    end--;
                }                
            } else if (nums[start] + nums[end] < target) {
                start++;
            } else if (nums[start] + nums[end] > target) {
                end--;
            }
        }
    }
}