LeetCode 1. 两数之和#

标签#

平台：LeetCode
难度：简单
数据结构：数组、哈希表
算法：枚举
解题模式：无

一、题目概述#

给定一个整数数组 nums 和目标值 target，需要在数组中找到两个不同位置的数，使它们的和等于 target，并返回这两个数的下标。当前实现如果没有找到结果，会返回空数组。

二、解题思路#

当前代码使用 HashMap 记录已经遍历过的数字和它的下标。遍历到 nums[i] 时，先计算当前数字需要的配对值 target - nums[i]，再去哈希表中查找这个配对值是否已经出现。

因为哈希表中只保存当前位置之前的元素，所以不会重复使用同一个下标。找到配对值后立即返回两个下标；如果遍历结束仍未找到，就返回空数组。

三、执行过程#

创建 hashMap，用于保存“数字 → 下标”。
从左到右遍历数组。
对当前数字 nums[i] 计算 need = target - nums[i]。
如果 need 已经在 hashMap 中，返回 need 的下标和当前下标。
否则把当前数字和下标放入 hashMap。
遍历结束仍没有结果时，返回 new int[0]。

例如 nums = [2, 7, 11, 15]，target = 9：遍历到 7 时，need = 2，哈希表中已经保存了 2 → 0，因此返回 [0, 1]。

四、代码实现#

1
public class LeetCode0001TwoSum {
2

3
    public static int[] twoSum(int[] nums, int target) {
4
        Map<Integer, Integer> hashMap = new HashMap<>();
5

6
        for (int i = 0; i < nums.length; i++) {
7
            int need = target - nums[i];
8

9
            if (hashMap.containsKey(need)) {
10
                return new int[]{hashMap.get(need), i};
11
            }
12

13
            hashMap.put(nums[i], i);
14
        }
15

16
        return new int[0];
17
    }
18
}

五、关键代码说明#

hashMap：保存已经遍历过的数字及其下标。
need：当前数字需要匹配的另一个数字。
containsKey(need)：判断之前是否出现过配对数字。
hashMap.put(nums[i], i) 放在查找之后，可以避免同一个元素被重复使用。
return new int[0] 是当前仓库实现定义的无解返回方式。

六、复杂度分析#

时间复杂度：O(n)，数组只遍历一次，哈希表查询平均为 O(1)。
空间复杂度：O(n)，最坏情况下哈希表会保存数组中的多数元素。

七、注意事项#

当前实现没有对 nums == null 做保护，传入 null 会触发空指针异常。
无解时返回空数组，这是当前实现行为，和部分平台“必有一解”的前提不同。
先查找再放入哈希表，才能避免同一个下标被使用两次。

八、面试知识点：HashMap#

1. 为什么两数之和会想到 HashMap？#

两数之和的核心问题是：遍历到 nums[i] 时，如何快速判断前面是否出现过 target - nums[i]。

如果使用两层循环，外层固定一个数，内层继续找另一个数，时间复杂度是 O(n^2)。当前实现使用 HashMap 保存已经遍历过的数字，把“查找某个值是否出现过”优化为平均 O(1)，整体时间复杂度就降为 O(n)。

这是一种典型的“用空间换时间”：额外使用一个哈希表，换来更快的查找速度。

2. 本题里的 HashMap 存什么？#

当前代码中：

key：已经遍历过的数组元素值；
value：这个元素在数组中的下标。

也就是：

1
Map<Integer, Integer> hashMap = new HashMap<>();

例如 nums = [2, 7, 11, 15]，target = 9：

遍历到 2 时，哈希表为空，先存入 2 -> 0；
遍历到 7 时，需要查找 9 - 7 = 2；
哈希表中已经存在 key 为 2 的记录，于是返回 [0, 1]。

3. 为什么先查找再插入？#

当前代码先执行：

1
if (hashMap.containsKey(need)) {
2
    return new int[]{hashMap.get(need), i};
3
}

再执行：

1
hashMap.put(nums[i], i);

这样可以避免同一个元素被使用两次。

例如 nums = [3]，target = 6。如果先把 3 放入哈希表，再查找 need = 3，就可能错误地把同一个下标当作两个数使用。先查找历史元素，再插入当前元素，可以保证找到的配对值一定来自当前下标之前的位置。

4. HashMap 的底层结构是什么？#

Java 8 之后，HashMap 的核心结构可以理解为：

1
数组 + 链表 + 红黑树

数组中的每个位置通常称为一个桶。插入一个 key-value 时，HashMap 会先根据 key 的哈希值计算它应该落在哪个桶里。

如果桶为空，直接放入节点；如果桶中已经有节点，说明发生了哈希冲突，会继续在这个桶对应的链表或红黑树中查找、插入或更新。

简化理解：

1
table[index]
2
    ├── Node
3
    ├── Node -> Node -> Node
4
    └── TreeNode 红黑树结构

5. 什么是哈希冲突？HashMap 如何解决？#

哈希冲突指的是：不同的 key 经过哈希计算后，落到了同一个数组桶中。

例如两个不同的 key 计算出的桶下标都是 5，它们就会争用同一个位置。

HashMap 主要使用链地址法解决冲突：同一个桶里的多个节点用链表连接起来。Java 8 之后，如果同一个桶里的节点过多，并且数组容量足够大，链表会转换成红黑树，以降低极端情况下的查找成本。

所以 HashMap 处理冲突的演进可以概括为：

1
少量冲突：数组桶 + 链表
2
严重冲突：数组桶 + 红黑树

6. 为什么 HashMap 的数组长度通常是 2 的幂？#

HashMap 需要根据 hash 值计算数组下标。数组长度是 2 的幂时，可以用位运算：

1
(n - 1) & hash

来代替取模运算：

1
hash % n

位运算通常更高效。

更重要的是，当 n 是 2 的幂时，n - 1 的二进制低位全是 1，可以更均匀地保留 hash 的低位信息，帮助元素分布到不同桶中。

扩容时也更方便。因为容量翻倍后，元素的新位置只会有两种情况：

1
仍在原下标
2
移动到 原下标 + oldCapacity

这使得扩容迁移不需要重新做完整取模计算。

7. 默认容量、负载因子和扩容阈值#

HashMap 的几个高频默认值：

默认初始容量：16
默认负载因子：0.75
扩容阈值：capacity * loadFactor

例如默认情况下：

1
capacity = 16
2
loadFactor = 0.75
3
threshold = 16 * 0.75 = 12

当元素数量超过 12 时，会触发扩容，通常扩容为原来的 2 倍。

负载因子表示哈希表允许被填满到什么程度。负载因子越高，空间利用率越高，但冲突可能更多，查找成本可能上升；负载因子越低，冲突更少，但会占用更多空间。默认的 0.75 是时间和空间之间的折中。

8. 链表什么时候转红黑树？#

Java 8 之后，HashMap 中单个桶的链表在满足条件时会转成红黑树：

桶内节点数达到 8；
并且数组容量至少为 64。

如果链表长度达到 8，但数组容量还小于 64，HashMap 会优先扩容，而不是立即树化。因为容量太小时，冲突可能只是数组太小导致的，扩容后节点可能会分散到不同桶中。

当红黑树中的节点数量减少到一定程度时，可能会退回链表。常见阈值是 6。这样可以避免节点数量在 8 附近反复变化时频繁树化和退化。

9. hashCode 和 equals 有什么关系？#

HashMap 查找 key 时，不是只看 hashCode，也不是只看 equals，而是两者都会用到。

基本规则：

如果两个对象通过 equals 判断相等，那么它们的 hashCode 必须相同；
如果两个对象的 hashCode 相同，它们不一定 equals 相等；
如果重写了 equals，通常必须同时重写 hashCode。

原因是 HashMap 会先用 hashCode 定位桶，再在桶内用 equals 判断是否是真正相同的 key。

本题使用的是 Integer 作为 key，Integer 已经正确实现了 hashCode 和 equals，所以不需要自己处理这些细节。

10. HashMap 的时间复杂度#

在哈希分布比较均匀的情况下：

put 平均时间复杂度：O(1)；
get 平均时间复杂度：O(1)；
containsKey 平均时间复杂度：O(1)。

如果大量 key 发生哈希冲突，并且都落到同一个桶里，链表结构下最坏可能退化到 O(n)。

Java 8 之后引入红黑树，冲突严重且满足树化条件时，桶内查找可以从链表的 O(n) 降到红黑树的 O(log n)。

所以本题复杂度分析里说时间复杂度是 O(n)，前提是 HashMap 的查找和插入按平均 O(1) 计算。

11. HashMap 是线程安全的吗？#

HashMap 不是线程安全的。

如果多个线程同时访问同一个 HashMap，并且至少有一个线程在做结构性修改，比如新增或删除 key，就需要额外同步。

面试中常见延伸对比：

Hashtable：线程安全，但方法级别同步，粒度较粗，性能较低；
Collections.synchronizedMap：把普通 Map 包装成同步 Map；
ConcurrentHashMap：并发场景更常用，设计上更适合高并发读写。

本题是单线程算法题，不涉及并发修改，所以直接使用 HashMap 即可。

12. 回到本题，面试时怎么回答？#

可以这样组织回答：

这道题的关键是快速判断补数是否已经出现过。我用 HashMap<Integer, Integer> 保存已经遍历过的数字和下标，其中 key 是数字，value 是下标。遍历当前数字 nums[i] 时，先计算 need = target - nums[i]，再用 containsKey 判断 need 是否在哈希表中。如果存在，就返回历史下标和当前下标；如果不存在，再把当前数字放入哈希表。这样可以避免同一个元素被重复使用。
相比双重循环的 O(n^2)，HashMap 的查找和插入平均是 O(1)，所以整体时间复杂度是 O(n)，空间复杂度是 O(n)。从 Java 实现看，HashMap 底层是数组、链表和红黑树，通过 hash 定位桶，通过链表或红黑树解决冲突。默认容量是 16，负载因子是 0.75，链表在节点数达到 8 且数组容量至少 64 时会转成红黑树。