Skip to main content

最长连续序列

Tips

题目类型: HashMap

题目​

给定一个未排序的整数数组 nums, 找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度.

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

提示:
  • 0 <= nums.length <= 10⁵
  • -10⁹ <= nums[i] <= 10⁹
示例
输入: nums = [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长数字连续序列是 [1, 2, 3, 4]. 它的长度为 4
输入: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
输出: 9

题解​

核心思路是判断每个数字是否为子序列的开头, 如果是开头, 再往后逐步加一找到最长连续子序列. 以 [100, 4, 200, 1, 3, 2] 为例:

  • 100 - 1 = 99 不存在于数组, 所以 100 就是子序列的开头, 然后让其 + 1 = 101 发现不存在于数组, 故以 100 开头的子序列最大连续子序列为 [ 100 ]
  • 4 - 1 = 3 存在于数组, 略过
  • 200 - 1 = 199 不存在于数组, 所以 200 就是子序列的开头, 然后让其 + 1 = 201 发现不存在于数组, 故以 200 开头的子序列最大连续子序列为 [ 200 ]
  • 1 - 1 = 0 不存在于数组, 所以 1 就是子序列的开头, 然后让其 + 1 = 2 发现存在于数组, 继续 + 1 直到加到 4, 故以 1 开头的子序列最大连续子序列为 [ 1, 2, 3, 4 ]
  • 3 - 1 = 2 存在于数组, 略过
  • 2 - 1 = 1 存在于数组, 略过

显然这是两层循环才能做到的事, 但题目要求 O(n) 复杂度, 所以可以通过一个 HashSet, 将获取元素的时间复杂度缩短到 O(1).

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  if (nums.length < 2) return nums.length

  const uniqueNums = new Set(nums)
  let max = 1

  for (const num of uniqueNums) {
    if (!uniqueNums.has(num - 1)) {
      let i = 1
      while (uniqueNums.has(num + i)) {
        i++
      }

      max = Math.max(max, i)
    }
  }

  return max
}