128. 最长连续序列

题目

力扣题目

给定一个未排序的整数数组 nums，找出数字连续的最长序列长度。序列中的元素不要求在原数组中连续。要求实现平均时间复杂度为 $O(n)$ 的算法。

示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
解释：最长连续序列是 [0,1,2,3,4,5,6,7,8]。

示例 3：

输入：nums = [1,0,1,2]
输出：3

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

考察内容

• 哈希集合的平均 $O(1)$ 查找
• 去重处理
• 识别连续序列的起点
• 避免对同一序列重复扫描
• 线性时间复杂度分析

解题思路

排序法

排序后可以跳过重复元素，并比较相邻数字是否相差 1。这种方法容易理解，但排序需要 $O(n\log n)$，不满足题目要求的 $O(n)$。

哈希集合 + 只从起点枚举

先将所有元素放入哈希集合，既可以去重，也能在平均 $O(1)$ 时间判断某个数字是否存在。

若对集合中的每个数都向后寻找连续数字，同一条序列会被重复扫描。例如 [1,2,3,4] 会分别从 1、2、3、4 开始扫描，最坏可能退化为 $O(n^2)$。

优化的关键是：只从连续序列的起点开始统计。

对于数字 num：

• 若集合中存在 num - 1，说明 num 前面还有连续数字，它不是起点，直接跳过；
• 若不存在 num - 1，说明 num 是起点，再依次检查 num + 1、num + 2……直到序列中断。

以集合 {100, 4, 200, 1, 3, 2} 为例：

虽然存在内层 while，但每个数字只会在所属序列从起点扩张时被访问一次。因此在哈希操作平均 $O(1)$ 的前提下：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

代码演示

int longestConsecutive(const std::vector<int>& nums) {
    std::unordered_set<int> values(nums.begin(), nums.end());

    int result = 0;

    for (int num : values) {
        // num - 1 不存在时，num 才是连续序列的起点
        if (!values.count(num - 1)) {
            int current = num;
            int length = 1;

            while (values.count(current + 1)) {
                ++current;
                ++length;
            }

            result = std::max(result, length);
        }
    }

    return result;
}

易错点

• 将“连续序列”理解为数组位置连续：题目只要求数值连续，元素在原数组中的顺序和位置不重要。
• 先排序再声称复杂度是 $O(n)$：排序法的整体复杂度是 $O(n\log n)$。
• 从每个数字开始向后枚举：会重复扫描相同序列，最坏退化为 $O(n^2)$。
• 没有先去重：重复数字不会延长连续序列；哈希集合可以自然去重。
• 判断错起点条件：起点的特征是 num - 1 不存在，而不是 num + 1 不存在。
• 空数组返回错误：集合为空时循环不执行，初始答案 0 即为正确结果。
• 忽略哈希表复杂度的含义：$O(n)$ 是基于哈希查找平均 $O(1)$ 得到的期望复杂度。

总结

哈希集合解决了“某个数字是否存在”的快速查询；只从没有前驱的数字开始扩张，则避免了重复工作。两者结合，才能得到平均 $O(n)$ 的解法。

相关题目

• 217. 存在重复元素
• 219. 存在重复元素 II
• 268. 丢失的数字
• 674. 最长连续递增序列
• 2007. 从双倍数组中还原原数组