128. Longest Consecutive Sequence
128. Longest Consecutive Sequence
题目
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 <= 10^5
-10^9 <= nums[i] <= 10^9
题目大意
给定一个未排序的整数数组,找出最长连续序列的长度。要求算法的时间复杂度为 O(n)
。
解题思路
- 遍历数组里的每个数
i
,以其为起点,寻找i+1, i+2, i+3...
是否存在,并不断记录以i
为起点时最长连续序列的长度; - 为了降低遍历数组的时间复杂度,可以将数组中的数存在哈希表中,这样查看一个数是否存在的时间复杂度可以优化到
O(1)
; - 为了去掉一些重复的枚举,可以只对
i-1
不存在的数i
为起点开始枚举;
代码
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
let set = new Set(nums);
let length = 0;
for (let item of [...set]) {
if (!set.has(item - 1)) {
let i = 1;
while (set.has(item + i)) {
i++;
}
length = Math.max(length, i);
}
}
return length;
};
相关题目
相关题目
- [🔒 Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence)
- [2177. 找到和为给定整数的三个连续整数](https://leetcode.com/problems/find-three-consecutive-integers-that-sum-to-a-given-number)
- [2274. 不含特殊楼层的最大连续楼层数](https://leetcode.com/problems/maximum-consecutive-floors-without-special-floors)
- [2414. 最长的字母序连续子字符串的长度](https://leetcode.com/problems/length-of-the-longest-alphabetical-continuous-substring)