128\. 最长连续序列
# 128. 最长连续序列 (opens new window)
# Description
Difficulty: 中等
Related Topics: 并查集 (opens new window), 数组 (opens new window), 哈希表 (opens new window)
给定一个未排序的整数数组 nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n)
的算法解决此问题。
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
1
2
3
2
3
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9
1
2
2
提示:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
# Solution
Language: JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
// 把题目中数组的数字全部放入set中,一来去重,二来方便快速查找
const set = new Set(nums);
let max = 0;
for (let val of nums) {
// 没有左邻居,是序列的起点,才开始数数
if (!set.has(val - 1)) {
let count = 1;
let now = val;
// 有右邻居,看连续的右邻居有多少个
while (set.has(now + 1)) {
now++;
count++;
}
// 存放最大的连续邻居的值
max = Math.max(max, count);
}
}
return max;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24