128. 最长连续序列

题目描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]

输出：9

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

出处：LeetCode

解法一：哈希表

思路

可以使用哈希表来解决这个问题。首先将所有的元素放入哈希表中，然后遍历数组中的每一个元素，对于每一个元素，我们检查其左右两侧是否有连续的元素，如果有，我们就将其从哈希表中删除，并更新当前连续序列的长度。最后我们返回最长的连续序列的长度。

代码

function longestConsecutive(nums: number[]): number {
  const numSet = new Set(nums);
  let longestStreak = 0;
  for (let num of numSet) {
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentStreak = 1;
      while (numSet.has(currentNum + 1)) {
        currentNum++;
        currentStreak++;
      }
      longestStreak = Math.max(longestStreak, currentStreak);
    }
  }
  return longestStreak;
}

上面的代码中：

1. 我们首先将所有的元素放入哈希表 numSet 中。
2. 然后遍历数组中的每一个元素 num，对于每一个元素，我们检查其左右两侧是否有连续的元素。如果没有，我们就将其从哈希表中删除，并更新当前连续序列的长度。
3. 最后我们返回最长的连续序列的长度。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度。我们需要 $O(n)$ 的时间来将所有的元素放入哈希表中，然后需要 $O(n)$ 的时间来遍历数组中的每一个元素。
• 空间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度。哈希表中最多包含 $n$ 个元素。

解法二：排序

思路

我们可以先对数组 nums 进行排序，然后遪行遍历数组，统计最长的连续序列的长度。

代码

function longestConsecutive(nums: number[]): number {
  if (nums.length === 0) {
    return 0;
  }
  nums.sort((a, b) => a - b);
  let longestStreak = 1;
  let currentStreak = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[i - 1]) {
      if (nums[i] === nums[i - 1] + 1) {
        currentStreak++;
      } else {
        longestStreak = Math.max(longestStreak, currentStreak);
        currentStreak = 1;
      }
    }
  }
  return Math.max(longestStreak, currentStreak);
}

上面的代码中：

1. 我们首先对数组 nums 进行排序。
2. 然后遍历数组，统计最长的连续序列的长度。
3. 注意：我们需要处理数组中有重复元素的情况。
4. 最后我们返回最长的连续序列的长度。

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是数组 nums 的长度。我们需要 $O(n \log n)$ 的时间对数组 nums 进行排序，然后需要 $O(n)$ 的时间遍历数组。
• 空间复杂度：$O(\log n)$，其中 $n$ 是数组 nums 的长度。空间复杂度取决于排序的栈空间。