题目

给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度。这里的”连续”不要求序列元素在原数组中相邻，并且题目要求时间复杂度为 O(n)。

示例

输入：nums = [100, 4, 200, 1, 3, 2]

输出：4

解释：最长连续序列是 [1, 2, 3, 4]，长度为 4。它由原数组中的 1、3、2、4 四个数构成，顺序无关紧要。

思路

先观察一下问题：我们要找的是”连续的数字段”。例如 1、2、3、4 是一段，100 单独是一段，200 单独是一段。数出一段有多长，本质上是在反复做一件事：判断某个数的下一个数在不在数组里。

如果每次判断都去数组里线性扫描，代价是 O(n)，整体会到 O(n²)。为了把这个判断变成 O(1)，先把全部数字放进一个哈希集合 unordered_set，它同时做了两件事：

  1. 去重。重复出现的数字不影响答案，集合天然去重。
  2. 让”判断 x 在不在”成为平均 O(1) 的查询。

集合建好后，遍历每个数 x：

  • 如果 x - 1 已经在集合里，说明 x 不是某个连续段的开头，跳过它。因为这一段会由更小的那个开头去统计，不必重复劳动。
  • 如果 x - 1 不在集合里，说明 x 是一个连续段的开头。从 x 开始向上数：x、x+1、x+2……直到某个数不在集合中，这一段就到头了，记录长度。
  • 每次统计完，更新目前遇到的最大长度。

这样每个连续段只被统计一次，不会超时。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int best = 0;
        for (int x : st) {
            if (st.count(x - 1)) continue;   // 不是段首，跳过
            int len = 1;
            while (st.count(x + len)) ++len; // 从段首向上数
            best = max(best, len);
        }
        return best;
    }
};

复杂度分析

设数组长度为 n。

  • 时间复杂度：建集合 O(n)；外层循环每个数一次判断 O(n)；所有 while 合计最多 n 步（每个数只可能被当作”段首”数一次，或作为段内后继被访问一次）。整体 O(n)。
  • 空间复杂度：集合存放全部数字，O(n)。

为什么不用排序

排序后相邻比较也能找出最长连续段，但排序本身是 O(n·log n)，不满足题目 O(n) 的硬性要求。哈希集合的代价是 O(n) 空间，换来的是 O(1) 的存在性判断，这是典型的用空间换时间。

两个容易忽略的点

  1. “只从段首数”这一步不能省。 如果去掉”x−1 存在就跳过”的剪枝，对每个数都盲目向上数，最坏会退化成 O(n²)。这个剪枝正是把整体控制在 O(n) 的原因。
  2. 遍历集合本身即可。 遍历 st 和遍历原数组结果一致，还天然去重；数组里的重复数字不会影响答案。

这类”判断元素是否存在”并要求 O(1) 的题目，第一选择是哈希集合。再加上”只从连续段起点统计”的剪枝，就同时保证了正确性和 O(n) 的复杂度。思路不复杂，代码也很短，难的是想清楚为什么不会超时。