两数之和：哈希表的极致应用，从O(n²)到O(n)的本质跨越

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约18分钟 | 难度：Easy

---

开篇故事

去年年底，我们组来了个应届生小王，简历上写着"熟悉常用数据结构与算法"。我当时负责技术面试，第一道题就给了他 LeetCode 1——两数之和。这道题说起来是 Easy，但我就想看看他能不能说出背后的思考过程。

小王盯着题目看了大概三分钟，然后开始写代码。双层 for 循环，暴力枚举，很快写完了。我问他："还有没有更好的方法？"他想了一会儿，说可以先排序然后双指针。我追问："排序之后下标就变了，你返回的是下标，这个方案有问题吗？"他愣住了。

后来他说其实知道哈希表，但没想清楚怎么用。这个回答让我有点遗憾——知道工具和能用好工具之间，差着一段真正的理解路程。

这道题我自己当年刷的时候也没少踩坑。第一次遇见它是2019年，刚开始系统刷题，看着 Easy 的标签以为随手就能过，结果也是先写了暴力，再被自己的 O(n²) 复杂度吓到，才开始认真想哈希的用法。

两数之和背后藏着一个非常本质的问题：我们为什么要用哈希表？哈希表解决的核心矛盾是什么？把这个问题搞透，后面一大片"用哈希优化查找"的题目都会豁然开朗。

---

一、题目解析

LeetCode 1. 两数之和（Two Sum）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

可以按任意顺序返回答案。

输入输出示例：

示例 1（基础情况）：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：nums[0] + nums[1] = 2 + 7 = 9

示例 2（目标元素不在首尾）：

输入：nums = [3,2,4], target = 6
输出：[1,2]
解释：nums[1] + nums[2] = 2 + 4 = 6

示例 3（两个相同的数字）：

输入：nums = [3,3], target = 6
输出：[0,1]
解释：同一个值出现两次，下标不同，合法

边界情况 4（负数参与运算）：

输入：nums = [-1,-2,-3,-4,-5], target = -8
输出：[2,4]
解释：nums[2] + nums[4] = -3 + (-5) = -8

边界情况 5（只有两个元素）：

输入：nums = [0,4], target = 4
输出：[0,1]

考察的核心知识点：

• 数组遍历
• 哈希表的 O(1) 查找能力
• 空间换时间的核心思想
• 补数关系的数学转换（target - nums[i] 是否存在）

---

二、解法一：暴力解法

思路分析

最直观的思路：遍历所有可能的两两组合，检查是否有一对数的和等于 target。

用数学来描述：对于数组下标 i 和 j（i ≠ j），找到满足 nums[i] + nums[j] == target 的那一对。

要枚举所有 (i, j) 的组合，一个外层循环跑 i 从 0 到 n-1，一个内层循环跑 j 从 i+1 到 n-1（注意 j 从 i+1 开始，避免重复对和使用同一元素）。每次检查 nums[i] + nums[j] 是否等于 target，相等就返回 [i, j]。

这个思路没有任何技巧，但它是理解后续优化的起点。我建议任何新题先在脑子里过一遍暴力解，不是因为暴力解有用，而是它帮助你明确"要找什么"。

这里有个细节值得注意：j 必须从 i+1 开始，而不是从 0 开始。如果从 0 开始，你可能会拿 nums[0] 和 nums[0] 相加，违反了"不能使用两次相同的元素"的约束。不过题目说的"相同的元素"指的是同一个位置的元素，所以如果数组里有两个 3，它们下标不同，是可以组成答案的。

完整 Java 代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        // 外层循环：固定第一个数的位置
        for (int i = 0; i < n - 1; i++) {
            // 内层循环：从 i+1 开始，避免重复使用同一位置
            for (int j = i + 1; j < n; j++) {
                // 检查两数之和是否等于目标值
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        // 题目保证有解，理论上不会到这里
        // 但 Java 编译器需要有返回值，加一个兜底
        return new int[]{-1, -1};
    }
}

复杂度分析

时间复杂度：O(n²)

推导过程：外层循环执行 n-1 次，对每个 i，内层循环执行 n-1-i 次。总操作次数 = (n-1) + (n-2) + ... + 1 = n*(n-1)/2。这是等差数列求和，结果是 n²/2 - n/2。忽略低阶项和常数系数，时间复杂度是 O(n²)。

空间复杂度：O(1)

除了结果数组，没有用到额外的数据结构。

缺陷与瓶颈

当数组长度 n = 10000 时，操作次数约为 5000 万次。在 LeetCode 上我提交过，运行时间大概在 80ms 左右，在测试用例规模大的时候会 TLE（超时限制）。实际业务中如果这个函数每秒被调用成千上万次，性能会是灾难。

---

三、解法二：排序+双指针（有缺陷的"优化"）

优化思路

有人可能会想到：先排序，然后双指针从两端向中间夹逼。这个想法来自"有序数组找两数之和"的经典做法，但在这道题里有个致命缺陷——题目要返回原始下标，排序之后下标就乱了。

如果题目只要求返回是否存在这样的两个数，或者返回具体的值，那排序+双指针是完全可以的。但这里要返回原始的 index，所以需要额外记录一下原始下标的映射。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 构造 [值, 原始下标] 的二维数组
        int n = nums.length;
        int[][] indexed = new int[n][2];
        for (int i = 0; i < n; i++) {
            indexed[i][0] = nums[i];
            indexed[i][1] = i;
        }
        // 按值排序
        Arrays.sort(indexed, (a, b) -> a[0] - b[0]);
        
        int left = 0, right = n - 1;
        while (left < right) {
            int sum = indexed[left][0] + indexed[right][0];
            if (sum == target) {
                // 返回原始下标，注意顺序
                int i = indexed[left][1];
                int j = indexed[right][1];
                return new int[]{Math.min(i, j), Math.max(i, j)};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

复杂度分析

时间复杂度：O(n log n)

排序是 O(n log n)，双指针遍历是 O(n)，总体由排序主导，为 O(n log n)。

空间复杂度：O(n)

需要额外的 indexed 数组存储原始下标信息。

这个解法比暴力好一些，但比哈希表解法差。而且代码复杂度明显上升，实际工程中不会这么写。它的主要价值是说明"排序+双指针"这个模式在有下标约束的时候需要特殊处理。

---

四、解法三：哈希表（工业级最优解）

核心洞见

暴力解法的本质问题在哪里？在于内层循环的查找是 O(n) 的。每次固定了 i，我们要在剩余的 n-1 个元素里查找是否存在 target - nums[i]。线性查找当然慢。

那怎么把这个查找变成 O(1)？答案就是哈希表——把"查找某个值是否存在"转换为"哈希表的 contains 操作"。

更精妙的地方在于：我们可以边遍历边建哈希表，不需要先把所有元素放进去再查找。

具体思路：维护一个 HashMap<Integer, Integer>，key 是已经见过的数组元素值，value 是它的下标。遍历到 nums[i] 时，先检查 target - nums[i] 是否已经在哈希表里。如果在，直接返回；如果不在，把 nums[i] 放进哈希表，继续遍历。

为什么这样是对的？因为如果答案是 (i, j) 且 i < j，那么当我们遍历到 j 时，i 已经被加入哈希表了，所以 target - nums[j] = nums[i] 能被查到。

这个"边走边建"的技巧在哈希表相关题目里非常常见，记住这个模式。

算法流程

完整 Java 代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // key: 数组元素的值, value: 该元素的下标
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 计算"另一个数"应该是多少
            int complement = target - nums[i];
            
            // 如果另一个数已经在哈希表里，找到答案
            if (map.containsKey(complement)) {
                // map.get(complement) 是另一个数的下标
                // 注意：先放入的是较小下标，所以结果顺序正确
                return new int[]{map.get(complement), i};
            }
            
            // 把当前元素放入哈希表，供后续元素查找
            // 注意：先查后放，避免用同一个元素两次
            // （如果先放，当 target = nums[i]*2 时，
            //   complement == nums[i]，会错误地用同一位置元素）
            map.put(nums[i], i);
        }
        
        // 题目保证有解
        return new int[]{-1, -1};
    }
}

复杂度分析

时间复杂度：O(n)

推导过程：只有一层 for 循环，循环体里的 containsKey 和 put 操作在哈希表中均为 O(1)（平均情况）。所以总时间是 O(n) × O(1) = O(n)。

严格来说，HashMap 的操作在最坏情况下（哈希冲突严重时）可以退化到 O(n)，但 Java 的 HashMap 在 JDK 8 之后引入了红黑树优化，实际工程中可以视为均摊 O(1)。

空间复杂度：O(n)

最坏情况下，答案在最后两个元素，我们需要把前 n-2 个元素都存入哈希表，空间是 O(n)。

我在 LeetCode 上提交这个解法，运行时间 2ms，击败了 99.1% 的 Java 用户。和暴力解法的 80ms 相比，差距一目了然。

---

五、举一反三

同类型题目

LeetCode 167. 两数之和 II - 输入有序数组

数组已经有序，直接用双指针，不需要哈希表，空间复杂度 O(1)。这道题和 1 的区别在于有序条件的利用。

LeetCode 653. 两数之和 IV - 输入 BST

给一棵二叉搜索树和目标值，找两个节点的值之和等于目标值。可以中序遍历后变成有序数组问题，或者用哈希表在遍历过程中记录已访问的值。

LeetCode 1. 拓展：三数之和（LeetCode 15）

两数之和的升级版。固定一个数，对剩余数组用双指针找两数之和等于 -nums[i]。这是下一篇的主题。

LeetCode 454. 四数相加 II

四个数组各取一个元素，和为 0 的方案数。用哈希表把四个数组分成两组，前两个数组的所有组合结果存入哈希表，再遍历后两个数组查找补数。

解题模板

遇到"找两个数满足某个条件，返回下标"的题型，先考虑哈希表：

// 通用模板：遍历+哈希查补数
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int need = 计算需要的补数(nums[i], target);
    if (map.containsKey(need)) {
        // 找到答案
        return result;
    }
    map.put(nums[i], i);  // 先查后放
}

关键判断：哈希表 vs 双指针

• 数组无序 + 需要原始下标 → 优先哈希表
• 数组有序 + 只需要值 → 优先双指针
• 数组无序 + 只需要值 → 排序后双指针，或者哈希表（看题目要求）

面试中的变体和追问

面试官可能会问的追问方向：

1. 如果数组中有重复元素怎么处理？（后出现的会覆盖前出现的，但题目说有唯一解，所以没问题）
2. 如果答案有多对怎么返回？（需要改成 List<int[]> 返回所有答案）
3. 哈希表的哈希冲突你了解吗？（拉链法 vs 开放寻址法）
4. 为什么要先查后放，而不是先放后查？（先放后查会导致 nums[i] + nums[i] 被错误匹配）

---

六、踩坑实录

坑一：先放后查导致用同一元素两次

现象： 输入 nums = [3, 2, 4], target = 6，正确答案是 [1, 2]，但代码返回了 [0, 0]。

等等，这个例子不对，3+3=6 但只有一个 3。我当时的坑是：输入 nums = [3, 3], target = 6 时，如果先把 nums[0]=3 放进 map，然后再查 complement=3 时，会在 map 里找到刚放进去的 nums[0]，返回 [0, 0]，两个 0 就是同一个位置的元素。

原因： 先放后查，自己匹配到了自己。

解法： 遍历时先查哈希表里有没有 complement，再把当前元素放入哈希表。这样当查找发生时，当前元素还没有进入 map，不会自匹配。

// 错误写法（先放后查）
map.put(nums[i], i);  // 先放
if (map.containsKey(target - nums[i])) {  // 后查，可能查到自己
    ...
}

// 正确写法（先查后放）
if (map.containsKey(target - nums[i])) {  // 先查
    ...
}
map.put(nums[i], i);  // 后放

坑二：HashMap 的 key 重复覆盖

现象： 数组中有重复元素，比如 nums = [2, 7, 11, 7], target = 14，答案应该是 [1, 3]，但代码可能返回错误结果。

原因： 当 nums[3]=7 入 map 时，会覆盖 nums[1]=7 的下标，导致哈希表里 key=7 对应的 value 变成了 3 而不是 1。但实际上这里要找的是 7+7=14，答案就是 [1, 3]，而当我们遍历到 i=3 时，先查找 complement=7，此时 map 里的 7 对应的是 index=1，刚好是正确答案，然后返回 [1, 3]。

等等，这里没问题？让我再想想。因为是先查后放，所以在 i=3 时，我们先查 complement=7，map 里此时 7 对应的是下标 1（从 i=1 放进去的），查到了，返回 [1, 3]，正确。

真正的问题是：如果 nums = [5, 2, 7, 5], target = 10，答案是 [0, 3]。遍历到 i=3 时，先查 complement=5，map 里有 5 对应下标 0，返回 [0, 3]，正确。

所以对于有唯一解的题目，这种覆盖不会导致错误。但如果题目要找所有答案，就需要改用 Map<Integer, List<Integer>> 存储同一个值的所有下标。

解法： 有唯一解时直接用，有多答案时改数据结构。

坑三：整数溢出问题（进阶变种）

现象： 如果题目变成四数之和，在计算中间累加值时，用 int 存储可能溢出。比如 nums[i] + nums[j] 两个 int 相加，结果如果超过 Integer.MAX_VALUE = 2147483647 就会溢出成负数。

原因： Java 的 int 是 32 位有符号整数，范围是 -2^31 到 2^31-1，约 ±21 亿。两个值在这个范围内的 int 相加，结果可能超出范围。

解法： 累加之前转 long，或者用 (long) nums[i] + nums[j] 强制提升类型。这道原题 nums[i] 范围是 -10^9 到 10^9，两个数相加最大 2×10^9，已经超过 int 最大值了。不过 LeetCode 的测试用例里 target 也在这个范围内，所以实际上不会出现这个边界情况，但养成用 long 的习惯很重要。

// 两数之和时不用担心，但三数、四数时务必注意
long sum = (long) nums[i] + nums[j] + nums[k];

---

七、总结

这道题表面简单，背后藏着算法优化的核心逻辑：识别瓶颈，用合适的数据结构消灭它。

暴力解法的瓶颈是内层的线性查找。哈希表把"在集合里找某个元素"从 O(n) 降到 O(1)，整体从 O(n²) 降到 O(n)。这个"查找加速"的思路在数十道 LeetCode 题里都用得上。

三条核心要点：

1. 哈希表的本质作用是把"查找"操作从 O(n) 降到 O(1)，代价是 O(n) 的额外空间——这是典型的空间换时间。

2. 先查后放的顺序非常关键，它保证了每次查找时当前元素不在 map 里，避免用同一个位置的元素两次。

3. 对于"找两个数满足条件+返回下标"的问题，哈希表几乎是标准答案；有序数组的变体可以考虑双指针节省空间。

延伸思考：

如果把这道题扩展成"在一个流式数据里，实时判断是否存在两个数之和等于目标值"，你会怎么设计？流式场景下不可能提前知道所有数，但可以维护一个哈希集合，每来一个新数就查找它的补数是否已经出现过。这就是两数之和的实时版本，在实际工程里比刷题时见得多得多。