What is the time complexity of the Longest Consecutive Sequence problem?

The optimal solution has a time complexity of O(n), where n is the number of elements in the array, due to the use of hash lookups.

How do you handle edge cases in the Longest Consecutive Sequence problem?

Edge cases such as an empty array or an array with only one element should be handled early to avoid unnecessary processing.

What data structure is used to efficiently solve the Longest Consecutive Sequence problem?

A hash set is used to store elements for fast lookup, enabling the solution to check consecutive sequences in constant time.

Can you solve the Longest Consecutive Sequence problem without sorting?

Yes, sorting the array is unnecessary. The problem can be solved using hash lookups, which ensures optimal time complexity of O(n).

Why does the Longest Consecutive Sequence solution need O(n) time?

The algorithm needs to scan the array once and check for consecutive sequences using constant-time hash lookups, making it efficient with a time complexity of O(n).

#128

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。示例 1：输入： nums = [100,4,200,1,3,2] 输出： 4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的…

数组哈希表并查集

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

输入：nums = [1,0,1,2]
输出：3

提示：

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：哈希表

我们可以用一个哈希表 $\textit{s}$ 存储数组中所有的元素，用一个变量 $\textit{ans}$ 记录最长连续序列的长度，用一个哈希表 $\textit{d}$ 记录每个元素 $x$ 所在的连续序列的长度。

接下来，我们遍历数组中每个元素 $x$ ，用一个临时变量 $y$ 记录当前连续序列的最大值，初始时 $y = x$ 。然后，我们不断尝试匹配 $y+1, y+2, y+3, \dots$ ，直到匹配不到为止，过程中将匹配到的元素从哈希表 $\textit{s}$ 中移除。那么，当前元素 $x$ 所在的连续序列的长度即为 $d[x] = d[y] + y - x$ ，然后更新答案 $\textit{ans} = \max(\textit{ans}, d[x])$ 。

遍历结束后，返回答案 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        ans = 0
        d = defaultdict(int)
        for x in nums:
            y = x
            while y in s:
                s.remove(y)
                y += 1
            d[x] = d[y] + y - x
            ans = max(ans, d[x])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to use a hash table for constant-time lookups?
question_mark
Can you explain why this solution guarantees O(n) time complexity?
question_mark
Will you consider edge cases such as empty arrays or single-element arrays?

warning

常见陷阱

外企场景

error
Relying on brute force methods like sorting or nested loops leads to suboptimal O(n log n) or O(n^2) time complexity.
error
Forgetting to handle edge cases, like arrays with one element or empty arrays, can lead to incorrect results.
error
Not using the hash table efficiently, such as by repeatedly checking for consecutive numbers instead of storing them all for quick lookups.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest consecutive sequence in a sorted array.
arrow_right_alt
Determine the longest consecutive subsequence in an array of integers with duplicates.
arrow_right_alt
Implement a solution using Union-Find to track consecutive sequences.

help

常见问题

外企场景

继续练习

#721 账户合并 #839 相似字符串组 #924 尽量减少恶意软件的传播