128. 最长连续序列

🟠   🔖  并查集 数组 哈希表  🔗 力扣 LeetCode

题目

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 为起点开始枚举；

复杂度分析

• 时间复杂度: O(n)，其中 n 是数组的长度，遍历了一遍数组。
• 空间复杂度: O(n)，使用了一个哈希表来存储数组中的数。

代码

/**
 * @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;
};

相关题目

题号	标题	题解	标签	难度
298	二叉树最长连续序列 🔒		树 深度优先搜索 二叉树
2177	找到和为给定整数的三个连续整数		数学 模拟
2274	不含特殊楼层的最大连续楼层数		数组 排序
2414	最长的字母序连续子字符串的长度		字符串
3020	子集中元素的最大数量		数组 哈希表 枚举