最长连续序列

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in \(O(n)\) time.

Example 1:

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

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]

Output: 9

Example 3:

Input: nums = [1,0,1,2]

Output: 3

Constraints:

• 0 <= nums.length <= \(10^5\)
• \(-10^9\) <= nums[i] <= \(10^9\)

Idea

Put all numbers into a hash set (such as set() in Python), which also removes duplicates. Searching for an element in a hash set takes \(O(1)\) time on average, so we can check whether a number exists without scanning the whole array.

A number \(x\) is the start of a sequence only if \(x - 1\) is not in the set. For each such start, count upward while \(x + 1, x + 2, \dots\) are in the set, and keep the longest length found. Numbers that are not starts are skipped, so each number is visited at most twice in total.

Loop over the set rather than nums, so a start that appears many times in nums is only counted once.

Time complexity: \(O(n)\), Space complexity: \(O(n)\), where \(n\) is the length of nums

Pseudo Code

set = hash set of all values in nums;
longest = 0;
for (x in set) {
    if (set.contains(x - 1)) {
        continue;                  // x is not the start of a sequence
    }
    length = 1;
    while (set.contains(x + length)) {
        length++;
    }
    longest = max(longest, length);
}
return longest;