从两数之和到四数之和：哈希与双指针的取舍

两数之和、三数之和、四数之和是同一道题的三个难度档位。把它们放在一起看，能看清一条主线：什么时候用哈希，什么时候排序后用双指针，以及去重为什么才是这类题的真正难点。

两数之和（1）：HashMap 一遍扫描

1 题返回的是下标，排序会打乱位置关系，哈希是首选：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // 值 -> 下标
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[]{seen.get(need), i};
            }
            seen.put(nums[i], i);   // 先查再存，天然避免用到自身
        }
        return new int[0];
    }
}

时间 O(n)、空间 O(n)。"先查再存"保证不会把同一个元素用两次。

三数之和（15）：为什么放弃哈希？

15 题返回的不是下标，而是值本身的三元组，且要求结果不重复。如果继续用哈希，难点会变成"如何在无序结构里表达 a ≤ b ≤ c 并完成去重"，写起来非常痛苦。

排序之后局面完全不同：

有序性让去重退化为"只跳过相邻重复"；
固定一个数 i 之后，找剩余两数变成有序数组上的对撞双指针，内层 O(n)。

整体 O(n²)，并且结果天然有序，去重规则清晰。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;                          // 剪枝：最小的数已为正，不可能凑出 0
            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) {
                    left++;                                   // 和偏小，左指针右移
                } else if (sum > 0) {
                    right--;                                  // 和偏大，右指针左移
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重②③：收集答案后，各自跳过连续相同的值
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

三层去重各司其职：

去重①（i 层）：nums[i] == nums[i-1] 时 continue，保证固定数不重复。注意比较对象是已经处理过的 i-1，不是 i+1。
去重②（left）：拿到一组答案后，left 连续跳过相同值。
去重③（right）：同理。

顺序也有讲究：先收集当前答案，再跳过重复，最后 left++/right-- 各进一步，先后颠倒就会漏解。

四数之和（18）：两层循环 + 剪枝 + long 防溢出

在 15 的外面再套一层：固定 i 和 j，内层对撞双指针。整体 O(n³)。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            // 剪枝①：以 i 开头的最小四数之和已超出 target，后面只会更大
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            // 剪枝②：以 i 开头的最大四数之和都不够 target，i 太小，换下一个
            if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
            if (i > 0 && nums[i] == nums[i - 1]) continue;             // 去重 i
            for (int j = i + 1; j < n - 2; j++) {
                // 同样的极值剪枝，作用在 [i 固定, j 起步] 的区间上
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;     // 去重 j
                int left = j + 1, right = n - 1;
                while (left < right) {
                    // 四个 int 相加可能溢出，先提升为 long 再比较
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;   // 去重 left
                        while (left < right && nums[right] == nums[right - 1]) right--; // 去重 right
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

18 题特有的两个坑：

target 不再是 0，剪枝不能照搬。15 题 nums[i] > 0 break 依赖"目标和为 0"；18 题的 target 可能是负数，nums[i] > target 时后面仍可能凑出解（如 target=-10、nums[i]=-3，但 -3-3-3-3=-12 可行）。正确的剪枝要用区间极值：当前范围的最小/最大四数之和与 target 比较，即代码中的剪枝①②。
long 防溢出：题目数据范围下四个 int 相加会超出 int 上限，必须先把其中一项提升为 long 再累加。

n 数之和的通用框架

规模	首选方法	循环结构	平均复杂度	关键点
两数之和（返回下标）	HashMap 一遍扫描	1 层	O(n)	先查再存
两数之和（有序/返回值）	排序 + 对撞双指针	1 层	O(n log n)	利用有序性
三数之和	排序 + 固定 1 个 + 对撞	2 层	O(n²)	三层去重
四数之和	排序 + 固定 2 个 + 对撞	3 层	O(n³)	极值剪枝 + long 防溢出
n 数之和	递归固定 n-2 个 + 对撞	n-2 层	O(n^(n-2))	通用递归框架

取舍口诀：要下标找哈希，要值先排序；层数决定复杂度，去重决定正确性。

再看一个对照组：454 四数相加 II 里四个数来自四个独立数组，不同下标的组合天然互不"重复"，不需要去重，用 HashMap 按两组之差统计反而最优。哈希与双指针的选择，本质上由三个问题决定：返回什么（下标/值）、是否有序、要不要去重。

易错点

去重①写成与 nums[i+1] 比较：会把"答案内部允许的重复值"整组跳过，必须与已处理的 i-1 比较。
收集答案后先 left++/right-- 再去重：连续重复值构成的解会漏掉。
15 题不写 nums[i] > 0 剪枝只是变慢；18 题照搬"与 target 直接比较"的剪枝则会错，必须用区间极值。
四数之和不用 long：大数相加溢出后 sum 比较结果错乱，解集残缺。

题目清单

题号	题名	一句话考点
1	两数之和	HashMap 先查再存，O(n)
15	三数之和	排序 + 对撞 + 三层去重
18	四数之和	两层固定 + 对撞 + long 防溢出
454	四数相加 II	四数组分组哈希，与 18 形成方法对照

参考

代码随想录 · 双指针法专题