最长连续序列 图解题解

题目要什么，难点藏在哪

给一个无序整数数组，求「数值上连续」的最长一段有多长——比如 [100,4,200,1,3,2,5,6] 里最长的是 1、2、3、4、5、6，答案 6。元素在原数组里的位置无关紧要，只看数值。真正的难点是题目附加的硬要求：时间复杂度必须 O(n)，这一刀直接把「先排序再扫一遍」的 O(n log n) 常规做法排除在正解之外。

为什么不能排序，暴力又卡在哪

排序做法思路简单：排完序连续的数就挨在一起，扫一遍统计最长连击即可，但排序本身 O(n log n)，不满足题目要求。另一个直觉是对每个数 x 都试着往上数：x+1 在不在、x+2 在不在……判断「在不在」若靠遍历数组是 O(n) 一次，整体最坏 O(n²)；就算用哈希集合把查询降到 O(1)，「每个数都往上数一遍」在数组本身就是一长串连续数时，仍会把同一段序列重复数 n 遍，还是 O(n²)。

关键观察：只从每段序列的起点开始数

省掉重复的办法是给「往上数」加一个准入条件：只有当 x - 1 不在集合里时才从 x 起步。x - 1 不存在，说明 x 是某段连续序列的最左端（起点）；反过来，只要 x - 1 存在，x 就处在别人的序列中段，从它数出来的一定是条被截短的重复子段，不数也罢。

这个小判断改变了整体的账：每段连续序列只会被它唯一的起点完整数一遍，序列内部的其他数只在准入判断时被看一眼。所有段加起来，每个元素最多被访问常数次，总时间稳稳落在 O(n)。

哈希集合在这里干了两件事

第一件是去重：set(nums) 把重复元素合并，重复的数既不该让序列变长，也会干扰起点判断，入集合时顺手解决。第二件是 O(1) 查询：无论是「x - 1 在不在」的起点判断，还是往上数时「cur + 1 在不在」的续链判断，都是一次哈希查找。整套算法就是「一次建集合 + 对每个集合元素做常数次查询」，没有任何排序或嵌套扫描。

复杂度怎么数出来，哪里容易翻车

时间 O(n)：建集合 O(n)；遍历集合时，非起点的数只花一次判断，起点的数把自己那段数完，每个元素作为「被数到的对象」恰好一次，两项相加仍是线性。空间 O(n)：集合存全部去重后的数。

最容易翻车的一处是漏掉「只从起点数」这个限制——代码能跑、答案也对，但复杂度退化成 O(n²)，大数据量直接超时，面试官追问复杂度时也答不上来。其次是遍历对象：第二遍循环应遍历去重后的集合而不是原数组，否则重复元素会让同一个起点被反复数。

Python

class Solution:
    def longestConsecutive(self, nums):
        num_set = set(nums)
        longest = 0
        for x in num_set:
            if x - 1 not in num_set:
                cur, length = x, 1
                while cur + 1 in num_set:
                    cur += 1
                    length += 1
                longest = max(longest, length)
        return longest

C++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int longest = 0;
        for (int x : s) {
            if (s.count(x - 1)) continue;
            int cur = x, length = 1;
            while (s.count(cur + 1)) {
                cur++;
                length++;
            }
            longest = max(longest, length);
        }
        return longest;
    }
};

Java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int longest = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int cur = x, length = 1;
            while (set.contains(cur + 1)) {
                cur++;
                length++;
            }
            longest = Math.max(longest, length);
        }
        return longest;
    }
}