128. Longest Consecutive Sequence

🟠   🔖  并查集 数组 哈希表  🔗 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 为起点开始枚举；

代码

/**
 * @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
• 2177. 找到和为给定整数的三个连续整数
• 2274. 不含特殊楼层的最大连续楼层数
• 2414. 最长的字母序连续子字符串的长度

- [🔒 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)