哈希表与连续序列：Two Sum 与 Longest Consecutive Sequence

摘要

本篇以 LeetCode 1（Two Sum）和 LeetCode 128（Longest Consecutive Sequence）为核心，深入讲解哈希表作为数组辅助数据结构的解题范式。Two Sum 是面试界的”Hello World”，几乎人人会做，但你真的理解它背后的设计权衡吗？Longest Consecutive Sequence 则是一道反直觉题——直觉告诉你”连续序列需要排序”，但哈希表能在 $O (n)$ 时间内解决。理解这两道题，你将掌握”以空间换时间”这一核心算法策略的精髓。

第 1 章哈希表： $O (1)$ 查询背后的代价

1.1 为什么需要哈希表

先回答一个基本问题：在已有数组、链表等基本结构的前提下，哈希表解决了什么问题？

数组的随机访问是 $O (1)$ ，但前提是”知道下标”。如果你只知道一个值，想在数组中查找它是否存在，只能线性扫描，是 $O (n)$ 。

哈希表（Hash Map / Hash Set）解决的问题是：给定一个任意的键（Key），在 $O (1)$ 时间内判断它是否存在，或者找到它对应的值。

这个能力在很多算法题中至关重要。比如 Two Sum：需要知道”数组中是否存在值为 target - nums[i] 的元素”，如果每次都线性扫描，是 $O (n)$ ，整个算法变成 $O (n^{2})$ ；用哈希表，查询降到 $O (1)$ ，整体降到 $O (n)$ 。

1.2 哈希表的工作原理（简要）

哈希表通过哈希函数将键映射到一个数组的下标：

$index = hash (key) mod capacity$

理想情况下，不同的键映射到不同的下标，查找就是”计算哈希值 → 直接读取”，是真正的 $O (1)$ 。

实际中不可避免存在哈希冲突（不同键映射到同一下标），通过链表法（每个槽维护一个链表）或开放寻址法解决。Java 的 HashMap 使用链表法，当链表过长时（默认阈值 8）会转换为红黑树，保证最坏情况 $O (lo g n)$ 。

哈希表的实际复杂度

哈希表的 $O (1)$ 是均摊和期望意义上的。如果哈希函数设计极差（所有键都映射到同一个槽），退化为 $O (n)$ 。实际工程中，Java HashMap、Python dict 的哈希函数设计得很好，碰撞极少，可以视为 $O (1)$ 。

另外，哈希表有扩容机制（负载因子超过阈值时扩容），扩容是 $O (n)$ 的，均摊到每次操作是 $O (1)$ 。

1.3 哈希表的代价

哈希表不是免费的午餐。它的代价是额外空间：存储哈希表本身需要 $O (n)$ 空间（ $n$ 是存储的键值对数量）。这正是”以空间换时间”的体现。

面试中，如果面试官问”能否用 $O (1)$ 空间解决”，通常意味着不能用哈希表，需要换思路（比如直接在输入数组上操作，或者排序后利用有序性）。

第 2 章 LeetCode 1：两数之和

2.1 题目

LeetCode 1 - Two Sum（简单）

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

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

输入: nums = [2,7,11,15], target = 9
输出: [0,1]（因为 nums[0] + nums[1] == 9）

输入: nums = [3,2,4], target = 6
输出: [1,2]

输入: nums = [3,3], target = 6
输出: [0,1]

2.2 从暴力到优化的推导过程

暴力解法：两层循环，枚举所有 $(i, j)$ 对，检查 nums[i] + nums[j] == target。

// 暴力解法：O(n²) 时间，O(1) 空间
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] == target) {
            return new int[]{i, j};
        }
    }
}

时间复杂度 $O (n^{2})$ ，对于 $n = 1 0^{4}$ ，是 $1 0^{8}$ 次操作，会超时。

如何优化？

关键观察：对于每个 nums[i]，我们需要找”是否存在另一个元素 nums[j] = target - nums[i]”。这是一个”查找”操作。

用线性扫描查找： $O (n)$ 每次，总体 $O (n^{2})$ ——和暴力一样
用哈希表查找： $O (1)$ 每次，总体 $O (n)$ ——这就是优化方向

单遍哈希表：不需要先把所有元素存入哈希表再查询，可以边遍历边存边查：

遍历到 nums[i] 时，先查哈希表中是否有 target - nums[i]（即我需要的”另一半”是否已经出现过），如果有则直接返回；如果没有，把 nums[i] 和其下标 i 存入哈希表，供后续元素查找。

public int[] twoSum(int[] nums, int target) {
    // key: 数组中的值，value: 该值的下标
    Map<Integer, Integer> seen = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i]; // 需要找的"另一半"
        
        if (seen.containsKey(complement)) {
            // 找到了！complement 的下标在哈希表里
            return new int[]{seen.get(complement), i};
        }
        
        // 没找到，把当前元素存入哈希表，供后续查找
        seen.put(nums[i], i);
    }
    
    return new int[]{}; // 题目保证有解，不会到达这里
}

2.3 为什么单遍就够？

有人会疑惑：单遍遍历时，对于靠后出现的元素，它”需要的另一半”可能还没存入哈希表，会不会漏掉？

不会，因为答案是一对 $(i, j)$ ，i < j。当我们遍历到 j 时，i 已经被存入哈希表了（因为 i < j，先遍历到）。所以到达 j 时，查哈希表一定能找到 i。

反过来，当我们遍历到 i 时，j 还没有被遍历，哈希表里没有 nums[j]，所以此时查不到，但我们会把 nums[i] 存入哈希表，等 j 遍历到时来查。

这个”边存边查”的技巧保证：对于任意一对有效答案 $(i, j)$ ，遍历到 j 时一定能找到 i（因为 i 更早被存入）。

2.4 处理重复元素

nums = [3, 3]，target = 6：

i=0：complement = 3，哈希表为空，未找到，存入 {3: 0}
i=1：complement = 3，哈希表中有 3 → 下标 0，返回 [0, 1]

两个相同的元素存在时，因为单遍策略的”先查后存”顺序，不会出现”用同一个元素两次”的问题：i=0 时查了哈希表（空的），没问题；i=1 时查到了 nums[0]=3，它的下标 0 不等于当前 1，是两个不同的位置。

2.5 复杂度分析

时间： $O (n)$ ，一次遍历，每次哈希查询和插入均为 $O (1)$
空间： $O (n)$ ，最坏情况哈希表存入所有 $n$ 个元素

这道题完美诠释了”以空间换时间”：额外付出 $O (n)$ 空间，换来时间从 $O (n^{2})$ 降到 $O (n)$ 。

2.6 如果数组有序：排序 + 双指针更优

如果题目条件改为”数组已排序，返回下标（1-indexed）“（LeetCode 167），可以用对撞双指针， $O (n)$ 时间 $O (1)$ 空间：

// 适用于有序数组的版本
int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return new int[]{left + 1, right + 1};
    else if (sum < target) left++;
    else right--;
}

为什么对撞双指针在有序数组上有效？因为有序性提供了单调性：当 sum < target 时，我们需要更大的和，而增大左指针（向右移）能让和变大（因为数组升序，右边的元素更大）；当 sum > target 时，减小右指针能让和变小。每次调整都是确定性的，不会遗漏答案。

这道题完整体现了算法的选择依据：

无序数组 + 返回下标 → 哈希表， $O (n)$ 时间 $O (n)$ 空间
有序数组 + 允许修改下标 → 对撞双指针， $O (n)$ 时间 $O (1)$ 空间
无序数组 + 要求 $O (1)$ 空间 → 先排序 $O (n lo g n)$ ，再双指针（但下标信息丢失，不适合返回下标的版本）

第 3 章 LeetCode 128：最长连续序列

3.1 题目

LeetCode 128 - Longest Consecutive Sequence（中等）

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 $O (n)$ 的算法解决此问题。

输入: nums = [100,4,200,1,3,2]
输出: 4（最长连续序列是 [1, 2, 3, 4]）

输入: nums = [0,3,7,2,5,8,1,4,6,9]
输出: 10（全部 10 个数字组成连续序列）

3.2 直觉陷阱：为什么不能用排序

第一直觉：排个序，然后线性扫描找最长连续段。逻辑清晰，代码也不复杂。

// 排序方案：O(n log n) 时间
Arrays.sort(nums);
int maxLen = 1, curLen = 1;
for (int i = 1; i < nums.length; i++) {
    if (nums[i] == nums[i-1] + 1) curLen++;
    else if (nums[i] != nums[i-1]) curLen = 1; // 跳过重复元素
    maxLen = Math.max(maxLen, curLen);
}
return maxLen;

这个方案完全正确，但时间复杂度是 $O (n lo g n)$ ，不满足题目 $O (n)$ 的要求。

题目明确要求 $O (n)$ ，这意味着不能排序，只能线性扫描。而线性扫描的核心困难是：数组无序，你不知道一个数字的前驱和后继在哪里。

解决方案：用哈希表存储所有元素，把”查询某个数是否存在”的代价降到 $O (1)$ ，从而可以在线性时间内”模拟排序后的遍历”。

3.3 哈希表方案的核心思路

关键洞察：只从每个连续段的起点开始扩展。

一个数 n 是连续段的起点，当且仅当 n-1 不在数组中（如果 n-1 存在，那 n 就不是起点，它是更长序列的中间或末尾部分）。

检测到起点后，从 n 开始，依次检查 n+1、n+2、n+3…是否在哈希表中，直到不在为止，就得到了以 n 为起点的连续段长度。

nums = [100, 4, 200, 1, 3, 2]
哈希表: {100, 4, 200, 1, 3, 2}

遍历每个元素，寻找起点：
- 100: 99 不在集合中 → 是起点！从 100 扩展：101 不存在，长度=1
- 4:   3  在集合中   → 不是起点，跳过
- 200: 199不在集合中 → 是起点！从 200 扩展：201 不存在，长度=1
- 1:   0  不在集合中 → 是起点！从 1 扩展：2存在→3存在→4存在→5不存在，长度=4
- 3:   2  在集合中   → 不是起点，跳过
- 2:   1  在集合中   → 不是起点，跳过

最大长度: 4

3.4 代码实现

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;
    
    // 用 HashSet 存储所有元素，O(n) 时间和空间
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) {
        numSet.add(num);
    }
    
    int maxLen = 0;
    
    for (int num : numSet) { // 遍历 set 而非原数组，自动去重
        // 只从起点开始扩展（num-1 不在集合中才是起点）
        if (!numSet.contains(num - 1)) {
            int currentNum = num;
            int currentLen = 1;
            
            // 向后扩展，直到找不到下一个数
            while (numSet.contains(currentNum + 1)) {
                currentNum++;
                currentLen++;
            }
            
            maxLen = Math.max(maxLen, currentLen);
        }
    }
    
    return maxLen;
}

3.5 时间复杂度为什么是 $O (n)$ ？

这道题最容易引起疑惑的地方是：外层 for 循环是 $O (n)$ ，内层 while 循环也可能执行多次，直觉上感觉是 $O (n^{2})$ 。

实际上是 $O (n)$ ，原因是”起点过滤”保证了 while 循环的总执行次数为 $O (n)$ 。

每个元素最多被 while 循环访问一次。为什么？因为 while 循环只从”起点”出发，而每个连续段只有一个起点，段内的元素只被它所属段的起点驱动一次扩展，不会被其他起点重复遍历（其他元素都因为”不是起点”而在 if 处被跳过）。

用更精确的语言说：外层循环的总执行次数是 $n$ ，内层 while 循环的所有轮次的总执行次数也是 $n$ （因为每个元素最多被 while 访问一次）。因此总时间是 $O (n) + O (n) = O (n)$ 。

这种分析方式叫分摊分析（Amortized Analysis），与动态数组扩容的分析是同一个道理。

设计哲学：用"入口控制"避免重复工作

这道题的精妙之处在于”只从起点出发”这个条件。它把一个潜在的 $O (n^{2})$ 操作（对每个元素都尝试向后扩展）变成了 $O (n)$ ，代价只是一个 $O (1)$ 的前置检查（num-1 是否存在）。这种”在入口处过滤，避免重复计算”的思路，在很多算法中都有体现。

3.6 与 Union-Find 的关系

Longest Consecutive Sequence 也可以用**并查集（Union-Find）**解决：初始时每个元素是独立集合，然后对每个元素 n，如果 n+1 存在就合并 n 和 n+1 所在的集合。最终找最大的集合。

并查集方案也是 $O (n)$ （路径压缩后均摊 $O (α (n))$ ，接近 $O (1)$ 每次操作），但代码更复杂。哈希表方案更简洁，面试中优先考虑哈希表方案。

第 4 章哈希表在线性表题中的通用应用模式

4.1 模式总结

哈希表在数组题中的典型应用场景：

场景	哈希表的作用	典型题目
查找补集	存储已见元素， $O (1)$ 查询”需要的另一半”是否存在	Two Sum（LeetCode 1）、3Sum（LeetCode 15）
判断存在性	快速判断某值是否在集合中，避免 $O (n)$ 扫描	Longest Consecutive Sequence（LeetCode 128）、Contains Duplicate
计数频次	统计每个元素出现次数，为后续操作提供信息	Single Number II（LeetCode 137）
记录位置	存储元素第一次出现的下标，用于计算长度	Longest Substring Without Repeating Characters

4.2 HashSet vs HashMap

面试题中有时用 HashSet（只需要判断存在性），有时用 HashMap（还需要记录下标或其他信息）：

HashSet：存值，查”某值是否存在”， $O (1)$ → 用于 Longest Consecutive Sequence
HashMap（key=值, value=下标）：存值和下标，查”某值是否存在以及它在哪里” → 用于 Two Sum

选择依据：题目是否需要返回下标？需要则用 HashMap，只需要判断存在则 HashSet 更简洁。

4.3 哈希表的常见陷阱

陷阱一：对同一元素查两次

Two Sum 中如果用两遍哈希（先全部存入，再逐个查），需要注意”不能用同一个元素两次”：

// 错误写法：查到的可能是自己
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) map.put(nums[i], i);
for (int i = 0; i < nums.length; i++) {
    int comp = target - nums[i];
    if (map.containsKey(comp) && map.get(comp) != i) { // 要检查下标不同
        return new int[]{i, map.get(comp)};
    }
}

单遍哈希（先查后存）天然避免了这个问题，是更推荐的写法。

陷阱二：HashMap 的 key 冲突

如果数组有重复元素，map.put(nums[i], i) 会用后面的下标覆盖前面的。对于 Two Sum，题目保证唯一解，这通常不是问题；但在需要记录所有出现位置的场景，需要 Map<Integer, List<Integer>>。

陷阱三：遍历 set 还是 array

Longest Consecutive Sequence 中，遍历 numSet（HashSet）而非原数组 nums，好处是自动去重。如果遍历原数组，遇到重复元素会多次触发 while 循环（虽然有起点过滤，但还是浪费），更清晰的做法是遍历去重后的集合。

第 5 章习题扩展

5.1 LeetCode 454：四数相加 II

四个数组 A, B, C, D，找 A[i] + B[j] + C[k] + D[l] = 0 的四元组数量。

思路：Two Sum 的扩展。把 A[i]+B[j] 的所有可能存入哈希表（计数），然后遍历 C[k]+D[l] 的所有可能，查哈希表找 -(C[k]+D[l]) 的计数。时间 $O (n^{2})$ 。

5.2 LeetCode 242：有效的字母异位词

判断两个字符串是否互为字母异位词（字母相同但顺序不同）。

思路：用哈希表统计字符频次，s 中每个字符 +1，t 中每个字符 -1，最后检查所有值是否为 0。可以用长度 26 的数组代替 HashMap（因为只有小写字母，26 个可能），空间更省。

5.3 延伸思考：时间与空间的权衡曲线

这两道题体现了一个普遍规律：降低时间复杂度通常需要增加空间。

方案	时间	空间	适用场景
Two Sum 暴力	$O (n^{2})$	$O (1)$	内存极度受限
Two Sum 哈希	$O (n)$	$O (n)$	常规场景
LCS 排序	$O (n lo g n)$	$O (1)$ 或 $O (n)$	对空间敏感
LCS 哈希	$O (n)$	$O (n)$	对时间敏感

在实际工程中，内存通常比 CPU 便宜， $O (n)$ 空间换 $O (n lo g n)$ 到 $O (n)$ 的时间降低是常见的优化手段。

下一篇预告

05 多指针夹逼：3Sum、3Sum Closest、4Sum 系列将进入”多数之和”专题。这类题是 Two Sum 的自然延伸，核心策略是”排序 + 降维”：把 k 数之和问题归约为 (k-1) 数之和，最终归约到 Two Sum（双指针或哈希）。重点难点是去重逻辑的正确性——如何在不漏解的情况下跳过重复三元组。

汀的知识碎片

文章导航

04 哈希表与连续序列：Two Sum 与 Longest Consecutive Sequence

哈希表与连续序列：Two Sum 与 Longest Consecutive Sequence

摘要

第 1 章哈希表： $O (1)$ 查询背后的代价

1.1 为什么需要哈希表

1.2 哈希表的工作原理（简要）

1.3 哈希表的代价

第 2 章 LeetCode 1：两数之和

2.1 题目

2.2 从暴力到优化的推导过程

2.3 为什么单遍就够？

2.4 处理重复元素

2.5 复杂度分析

2.6 如果数组有序：排序 + 双指针更优

第 3 章 LeetCode 128：最长连续序列

3.1 题目

3.2 直觉陷阱：为什么不能用排序

3.3 哈希表方案的核心思路

3.4 代码实现

3.5 时间复杂度为什么是 $O (n)$ ？

3.6 与 Union-Find 的关系

第 4 章哈希表在线性表题中的通用应用模式

4.1 模式总结

4.2 HashSet vs HashMap

4.3 哈希表的常见陷阱

第 5 章习题扩展

5.1 LeetCode 454：四数相加 II

5.2 LeetCode 242：有效的字母异位词

5.3 延伸思考：时间与空间的权衡曲线

下一篇预告

On this page

Backlinks

汀的知识碎片

文章导航

04 哈希表与连续序列：Two Sum 与 Longest Consecutive Sequence

哈希表与连续序列：Two Sum 与 Longest Consecutive Sequence

摘要

第 1 章 哈希表：O(1) 查询背后的代价

1.1 为什么需要哈希表

1.2 哈希表的工作原理（简要）

1.3 哈希表的代价

第 2 章 LeetCode 1：两数之和

2.1 题目

2.2 从暴力到优化的推导过程

2.3 为什么单遍就够？

2.4 处理重复元素

2.5 复杂度分析

2.6 如果数组有序：排序 + 双指针更优

第 3 章 LeetCode 128：最长连续序列

3.1 题目

3.2 直觉陷阱：为什么不能用排序

3.3 哈希表方案的核心思路

3.4 代码实现

3.5 时间复杂度为什么是 O(n)？

3.6 与 Union-Find 的关系

第 4 章 哈希表在线性表题中的通用应用模式

4.1 模式总结

4.2 HashSet vs HashMap

4.3 哈希表的常见陷阱

第 5 章 习题扩展

5.1 LeetCode 454：四数相加 II

5.2 LeetCode 242：有效的字母异位词

5.3 延伸思考：时间与空间的权衡曲线

下一篇预告

On this page

Backlinks

第 1 章哈希表： $O (1)$ 查询背后的代价

3.5 时间复杂度为什么是 $O (n)$ ？

第 4 章哈希表在线性表题中的通用应用模式

第 5 章习题扩展