128. 最长连续序列 (Medium)

专题归类： 01-哈希表 · 03-数组 LeetCode 链接： https://leetcode.cn/problems/longest-consecutive-sequence/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

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

示例：

输入：nums = [100, 4, 200, 1, 3, 2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]，长度为 4

补充说明：

• 数组长度范围：0 <= nums.length <= 10^5
• 数值范围：-10^9 <= nums[i] <= 10^9

---

题目详细分析

数据范围含义：

• 数组最长 10^5，允许 O(n log n) 乃至 O(n^2) 的朴素解法？不行，题目明确要求 O(n)，这是一个强约束，直接排除了排序法（O(n log n)）和暴力法（O(n
• 数值范围 ±10
• 数组长度可以为 0，此时最长连续序列长度为 0。

输入输出特征：

• 输入完全无序，不能指望有任何顺序信息。
• 输出是一个整数，表示最长连续序列的长度。
• 注意”序列”在这里指数值上连续（如 1,2,3,4），而不是在原数组中的位置连续。

核心约束：

• O(n) 时间复杂度是最大的挑战。这要求每个元素的处理时间必须是 O(1) 摊销。
• 不能排序（排序就是 O(n log n)）。

隐藏条件：

• 重复元素不影响结果——[1, 2, 2, 3] 的最长连续序列是 3 而非 4，因为重复的 2 不计入长度。
• 题目不要求返回具体的序列，只需要长度，这降低了复杂度。

---

小白版直白理解

想象你在整理一堆彩票号码。你想知道最长的”连号”有多长——比如你手上有 1, 3, 2, 4, 100, 200，那最长的连号就是 1-2-3-4，长度 4。

笨办法（排序法）： 把号码从小到大排好，然后看哪些是连续的。但排序就要花不少时间，不符合要求。

聪明办法（哈希集合法）： 先把所有号码写进一个本子（哈希集合），然后一个个检查。

关键窍门是：只从每个”连续串”的开头开始数。比如数字 100，你要先看 99 在不在本子里？不在！那 100 就是一个连续串的开头，从它往后数 101、102……看能连续多少个。

而数字 3，你要先看 2 在不在本子里？在！说明 3 不是开头，跳过它不管。这样就避免了重复计算——每个数字最多被访问两次（一次检查是否是开头，一次作为开头往后延伸）。

---

解题思路

思路一：哈希集合 + 起点查找（推荐）

关键洞察： 如果不做优化，对每个元素都往后查找连续序列，最坏情况 O(n^2)。例如 [1, 2, 3, 4, 5]——每个元素都会往后找一遍。

核心优化：只从序列的起点开始查找。 如何判断一个数字是起点？检查 num - 1 是否在集合中。如果不在，说明 num 是一个连续序列的第一个元素；如果在，说明 num 不是起点，跳过它。

这个优化的美妙之处在于：每个元素最多被”往后延伸”一次（只有当它是起点时），总体 O(n)。

def longestConsecutive(nums):
    """
    哈希集合 + 起点查找
    只从序列的起点开始向后延伸
    
    步骤：
    1. 将所有元素放入集合（去重）
    2. 遍历集合，只对 num-1 不在集合中的元素（即起点）进行延伸
    3. while 循环检查 current+1 是否在集合中
    4. 更新全局最大长度
    """
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        # 只从序列起点开始查找
        if num - 1 not in num_set:
            current = num
            length = 1
            
            # 向后延伸，查找连续数字
            while current + 1 in num_set:
                current += 1
                length += 1
            
            longest = max(longest, length)
    
    return longest

思路二：排序 + 扫描（不满足 O(n)，但思路简单）

先排序，再遍历一次。遇到连续的数字计数加 1，遇到不连续的重置计数，遇到重复的跳过。

虽然清晰易懂，但排序本身就是 O(n log n)，不满足题目要求。

def longestConsecutive_sort(nums):
    if not nums:
        return 0
    nums.sort()
    longest = 1
    cur_len = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            # 重复元素，跳过
            continue
        elif nums[i] == nums[i-1] + 1:
            # 连续，延长
            cur_len += 1
        else:
            # 断开了，重置
            longest = max(longest, cur_len)
            cur_len = 1
    return max(longest, cur_len)

思路三：并查集（Union-Find，进阶）

可以用并查集将连续的数字合并到同一个集合中，每个集合维护一个 size。最终找最大的 size。

虽然有趣，但实现比哈希集合法复杂，在面试中不推荐作为首选。

---

易错点

• 重复元素： nums = [0, 0, 1, 2]，最长的连续序列是 [0, 1, 2] 长度 3，不是 4。必须用 set 去重，否则重复的 0 会被多算。
• 空数组： nums = [] 直接返回 0。如果没有空值检查，set() 会在 for 循环中正常处理（不进入循环，返回 0），但排序法需要显式处理。
• 遍历 set 而非原数组： 在 for 循环中应该遍历 num_set 而不是 nums。这样可以减少重复元素带来的不必要检查。
• 负数处理： num - 1 not in num_set 对负数同样有效，不需要特殊处理。
• 溢出不需担心： Python 的 int 是任意精度的，±10^9 范围内没问题。

---

框架提炼

哈希集合 + 起点查找模板：

这类问题的核心模式是：跳过非起点，只从起点延伸。

def find_consecutive(nums):
    """
    哈希集合 + 起点查找 通用模板
    """
    # 1. 去重
    elements = set(nums)
    max_count = 0
    
    for x in elements:
        # 2. 判断是否为起点（前驱不在集合中）
        if x - 1 not in elements:
            # 3. 从起点向后延伸
            current = x
            count = 0
            while current in elements:  # 或 current + step in elements
                count += 1
                current += 1  # 或 current += step
            # 4. 更新最优解
            max_count = max(max_count, count)
    
    return max_count

适用场景特征：

• 需要在无序数组中找连续/递增的序列
• 有 O(n) 的时间复杂度要求
• 通过”跳过非起点”避免 O(n^2) 的重复计算

---

关联题目

• 1-两数之和 — 同样使用哈希表来实现 O(1) 查找，但两数之和是查找 target - num，本题是查找 num + 1（向后延伸）
• 49-字母异位词分组 — 同样是哈希表 + 数组类问题，但”分组”用的是哈希表不同的功能维度
• 674-最长连续递增序列 — 本题的简化版，但要求在数组中的位置也连续（子数组），可以用一次遍历解决，不需要哈希表