题目描述#

题目链接

1
input: nums = [100,4,200,1,3,2]
2
output: 4

1
input: nums = [0,3,7,2,5,8,4,6,0,1]
2
output: 9

1
input: nums = [1,0,1,2]
2
output: 3

解题思路#

题目要求找出数组中数值连续的最长序列长度，这里的”连续”指的是数字本身相差 1，并不要求它们在原数组中下标相邻。

很容易想到先排序再从头扫描统计连续段长度，比如 [100,4,200,1,3,2] 排序后变成 [1,2,3,4,100,200]，扫一遍就能数出最长段。但排序至少需要 $O(n \log n)$，题目明确要求 $O(n)$，此路不通。

既然不能排序，又要快速判断某个数是否在集合中，我们在前两题学过的哈希集合就派上用场了——set 的查询是 $O(1)$ 的，还能顺便去重。

一个自然的想法是：把 nums 转成 set，对每个数 x 不断检查 x+1、x+2……是否在集合里，统计长度。但这样会有大量重复计算——比如序列 [1,2,3,4]，从 1 往上数一遍，从 2 又往上数一遍，最坏会退化到 $O(n^2)$。

怎么避免重复？关键思路是：每条连续序列只需要统计一次。常见做法是从序列的左端点入手——若 x - 1 在集合中，说明 x 不是开头，直接跳过；否则从 x 向右扩展统计长度。

我们的做法是对称的：从序列的右端点入手。遍历集合中的每个 x，若 x + 1 还在集合里，说明 x 不是某段连续序列的最大值，跳过；只有当 x + 1 不存在时，x 才是一段连续序列的右端点。

确认 x 是右端点后，向左”顺藤摸瓜”：令 t = x，不断 t -= 1，直到 t 不在集合中为止。此时 t 恰好落在连续段左端点的左边一位，因此这段序列的长度就是 x - t。

以 nums = [100,4,200,1,3,2] 为例，去重后集合为 {1,2,3,4,100,200}：

• 1、2、3 的右邻 +1 都在集合中，跳过
• 遇到 4：5 不在集合中，向左走 4→3→2→1→0，t 停在 0，长度 4 - 0 = 4
• 100、200 各自成段，长度均为 1

每条连续序列只在处理其最大值时统计一次，每个数最多被向左访问一次，总时间复杂度 $O(n)$，空间复杂度 $O(n)$。

1
class Solution:
2
    def longestConsecutive(self, nums: List[int]) -> int:
3
        nums = set(nums)
4
        ans = 0
5
        for x in nums:
6
            if x + 1 in nums: continue
7
            t = x
8
            while t in nums: t -= 1
9
            ans = max(ans, x - t)
10
        return ans