跳到主要内容

LeetCode 128. 最长连续序列

本节目标

用集合判断相邻数是否存在，并只从连续序列起点向后扩展。

这道题承接哈希表解题框架：查询只需要回答“相邻值是否存在”，因此用集合即可，不必为每个值保存附加信息。

查看原题

题意与约束​

给定一个未排序整数数组，返回最长连续整数序列的长度。序列中的数字不要求在原数组中相邻，例如 [100, 4, 200, 1, 3, 2] 的最长连续序列是 1, 2, 3, 4。

排序后扫描能够解决问题，但需要 O(n log n) 时间。目标是让每个数字的相邻关系通过集合的成员查询直接得到。

只从没有前驱的值开始​

先把所有数字放进集合。对值 x，若 x - 1 也在集合中，x 一定是某段连续序列的中间部分；从它开始向后数会和更早的起点重复工作。只有 x - 1 不在集合中时，x 才是该段序列唯一的起点。

从起点开始不断查询 x + 1、x + 2，直到下一个数不存在。每次得到的长度与当前最优答案比较。集合同时去除了原数组中的重复值，所以重复输入不会触发重复扩展。

为什么总扩展次数是线性的​

把集合中的不同值按连续段划分。每一段只会被它的最小值启动一次；段内其他值都有前驱，外层循环会跳过它们。启动后向前推进时，段内每个元素只被有效访问一次。

因此，尽管某个起点可能走很长，所有段的有效向后访问次数相加不超过不同元素数 m。外层的集合遍历也是 m 次，成员查询期望为常数时间，整体是均摊线性，而不是对每个元素再扫描一遍。

代码实现​

C++ 使用 unordered_set，Python 使用 set。二者都先建立集合，再只从前驱缺失的值开始延伸；没有数字时集合为空，答案保持为 0。

C++17
#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> values(nums.begin(), nums.end());
        int longest = 0;

        for (int value : values) {
            if (values.count(value - 1) > 0) {
                continue;
            }

            int current = value;
            int length = 1;
            while (values.count(current + 1) > 0) {
                current++;
                length++;
            }
            longest = max(longest, length);
        }
        return longest;
    }
};

复杂度分析​

  • 时间复杂度：期望 O(n)。建集合和遍历不同元素为线性，按上述摊还分析，向后扩展的有效访问总数也是线性。
  • 空间复杂度：O(n)。集合保存数组中的不同值。

易错点​

  • 从每个值都向后扩展：连续段很长时会重复计数，最坏退化为平方级。
  • 直接沿原数组下标寻找连续数：题目只关心数值相邻，原数组顺序没有意义。
  • 忽略重复值：若不先去重，重复输入会让同一段被多次处理。
  • 把没有前驱的判断写反：应在 x - 1 不存在时才开始。

模式迁移​

这题的核心是“只从规范起点展开”。区间合并可只从最左端开始，字符串分段可只从合法起点开始，图搜索可用访问集合阻止重复扩展。需要同时维护存在性和访问顺序时，则要转向LRU 缓存这样的组合结构。