无序数组的两数之和为什么用哈希表？

简化版

无序数组两数之和用哈希表一边遍历一边查 target - nums[i] 是否出现过。哈希表保存“值到下标”的映射，平均 O(1) 查补数，所以整体从暴力 O(n²) 降到 O(n)，空间 O(n)。

详细版

暴力枚举所有二元组会重复比较。哈希表的思路是：当前数是 x，只要之前出现过 target - x，答案就找到了；否则把 x 存进去，等待后面的数来匹配。

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[] {-1, -1};
}

要先查再放，避免同一个元素被自己使用。数组无序时，双指针没有方向依据，哈希表是最直接的高频解法。

完整版教学

一、题目考的不是加法，而是“查补数”

两数之和给定 nums 和 target，要找两个不同下标 i、j，满足 nums[i] + nums[j] = target。把式子变形就是：当我们看到 nums[i] = x 时，需要知道前面有没有 target - x。所以核心操作是“快速判断某个值是否出现过”。

例如 nums=[2,7,11,15], target=9，看到 2 时需要 7，还没有；看到 7 时需要 2，哈希表里已经有，于是返回 [0,1]。

二、为什么暴力是 O(n²)

暴力做法固定第一个数，再在后面找第二个数。长度为 5 时，最多比较 4+3+2+1=10 次；长度为 n 时，比较次数约为 n(n-1)/2。

i=0: compare with 1,2,3,4
i=1: compare with 2,3,4
i=2: compare with 3,4

这个重复枚举没有利用“一个数只需要找它的补数”这一结构。哈希表恰好把“找补数”变成平均 O(1)。

三、哈希表里存什么

常见需求是返回下标，所以哈希表存 value -> index。如果题目只问是否存在，可以存 HashSet<Integer>；如果可能有重复值且要返回所有组合，就要存值到多个下标或先统计次数。

题目要求	哈希结构	例子
返回一组下标	`Map<值, 下标>`	LeetCode 1
判断是否存在	`Set<值>`	是否有两数和
统计组合数	`Map<值, 次数>`	多个重复值

选结构时要围绕“答案需要什么信息”来定，不要机械套 Map。

四、为什么必须先查再放

如果先把当前数放进表，再查补数，会在 target = 2 * nums[i] 时误用同一个下标。例如 nums=[3], target=6，先放 3 再查 3，就会错误命中自己。

正确顺序:
1. need = target - nums[i]
2. 查 need 是否在 seen
3. 把 nums[i] 放入 seen

这个顺序保证哈希表里只包含当前元素左边的元素，下标天然不同。

五、重复值和覆盖问题

如果数组有重复值，例如 [3,3], target=6，第一个 3 存入表，第二个 3 查到第一个 3，答案成立。seen.put(nums[i], i) 是否覆盖旧下标，通常不影响“返回任意一组答案”的题；但如果题目要求所有答案，就不能简单覆盖。

复杂度上，每个元素只处理一次，哈希表平均查找和插入 O(1)，所以时间 O(n)，空间最多存 n 个元素。

六、常见误区与追问

记忆钩子：两数之和的哈希表不是存答案，而是存“之前见过谁”，当前数只负责找自己的补数。

误区：先 put 再查也一样。 这样可能把同一个元素当成两次使用，必须先查再放。
误区：无序数组也能直接双指针。 双指针需要有序性决定移动方向，无序时移动没有排除依据。
误区：哈希表一定严格 O(1)。 平均 O(1)，严重冲突时会退化，工程实现靠扩容和冲突治理缓解。
追问：如果数组已排序怎么办？ 可以用双指针 O(n) 时间、O(1) 空间，但要注意返回原下标的需求。
追问：如果要返回所有组合怎么办？ 需要处理重复值和去重策略，常用计数表或排序后双指针。
追问：为什么 Map 存下标不存布尔值？ 因为题目通常要返回下标；只判断存在时 Set 就够。

七、加强记忆

无序两数之和的主线是：当前数 x 需要补数 target-x，哈希表保存已经看过的值和下标。先查补数再放当前数，既避免自匹配，又让每个元素只扫一遍。看到“无序 + 快速找另一个值”，优先想到哈希查补。

简化版

详细版