最长连续序列(LeetCode 128)如何在 O(n) 内求解?
哪些公司问过
答案要点
- 用哈希集合存放所有元素,自动去重,查询 O(1)
- 只从起点开始计数:x-1 不在集合中时,x 才是连续段的起点
- 从起点向后查 x+1、x+2……统计长度并更新最大值
- 每个元素最多被访问两次,时间 O(n),空间 O(n)
- 边界:空数组返回 0;排序法为 O(n log n),不满足题目要求
易错点
- 对每个数都向后扫描而不判断是否为起点,最坏退化到 O(n²)
- 先排序再扫描,复杂度 O(n log n),不满足题目要求
- 排序解法中没处理重复元素,导致连续长度被中断
面试官常见追问
- 为什么遍历集合而不是遍历原数组?
- 能不能用并查集来做?
- 如果要求返回序列本身而不只是长度呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。