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
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
Solutions
Solution 1: Sorting
First, we sort the array, then use a variable $t$ to record the current length of the consecutive sequence, and a variable $ans$ to record the length of the longest consecutive sequence.
Next, we start traversing the array from index $i=1$. For the current element $nums[i]$:
If $nums[i] = nums[i-1]$, it means the current element is repeated and does not need to be considered.
If $nums[i] = nums[i-1] + 1$, it means the current element can be appended to the previous consecutive sequence to form a longer consecutive sequence. We update $t = t + 1$, and then update the answer $ans = \max(ans, t)$.
Otherwise, it means the current element cannot be appended to the previous consecutive sequence, and we reset $t$ to $1$.
Finally, we return the answer $ans$.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.
usestd::collections::HashSet;implSolution{#[allow(dead_code)]pubfnlongest_consecutive(nums:Vec<i32>)->i32{letmuts=HashSet::new();letmutret=0;// Initialize the setfornumin&nums{s.insert(*num);}fornumin&nums{ifs.contains(&(*num-1)){continue;}letmutcur_num=num.clone();whiles.contains(&cur_num){cur_num+=1;}// Update the answerret=std::cmp::max(ret,cur_num-num);}ret}}
We use a hash table to store all elements in the array, and then traverse each element $x$ in the array. If the predecessor $x-1$ of the current element is not in the hash table, then we start with the current element and continuously try to match $x+1, x+2, x+3, \dots$, until no match is found. The length of the match at this time is the longest consecutive sequence length starting with $x$, and we update the answer accordingly.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.