128. 最长连续序列（中等）

Blind 75 › 128. 最长连续序列（中等） （第 8 章）
文章工具

题目

给定一个未排序的整数数组，返回「数字连续」的最长序列长度。这里的连续只要求数值一个接一个（相邻差 1），不要求这些元素在原数组中的位置连续。

自造示例：nums = [7, 3, 5, 4, 6, 1, 2]，其中 [1, 2, 3, 4, 5, 6, 7] 连续且长度为 7，所以返回 7。

再如 nums = [5, 2, 99, 3, 1]，最长连续序列是 [1, 2, 3]，返回 3。

约束：数组长度 0 ~ 105；元素范围 -109 ~ 109；要求时间复杂度 O(n)。

思路

一句话：把数组放进哈希集合去重，只从「每个连续段的起点」开始向后数。

先想最直白的：对每个数 x，依次找 x+1、x+2、… 在不在数组里。每次查找若线性扫描是 O(n)，整体会到 O(n³)；就算先把查找换成集合 O(1)，如果每个数都当起点向后数，最坏仍是 O(n²)——例如 [1,2,…,n]，第 i 个数要向后数 n-i 次，总共约 n²/2 次。

排序是另一条路：排完序后扫相邻差即可，时间 O(n log n)。它能解，但不满足题目要求的 O(n)。

关键观察：一条连续序列 [a, a+1, …, b] 里，只有 a 满足「a-1 不在集合中」，称它为起点。若 x-1 已经在集合里，说明 x 会被更小的数“带着数到”，不必从它开始。因此只对起点执行向后数，每个数最多被数一次。

于是用哈希集合去重 + O(1) 判断存在：遍历集合

🔒

本篇为付费内容

您已阅读试读部分，购买后即可解锁全文。

⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。