1. 题目描述

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

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

示例 1：

  1. 输入：nums = [100,4,200,1,3,2]
  2. 输出：4
  3. 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

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

提示：

  • 0 <= nums.length <= 10
  • -10 <= nums[i] <= 10

    2. 解题思路

    这个题目一个比较直接的思路就是，将数组元素进行排序，然后遍历数组，对比相邻的元素，如果相差1，就加一，否则就继续遍历。维护一个最大的长度，最后返回最大长度即可。

不过，这种方式并没有达到题目要求的O(n)的时间复杂度。

复杂度分析：

  • 时间复杂度：O(nlogn)

  • 空间复杂度：O(n)

    3. 代码实现

    1. /**
    2. * @param {number[]} nums
    3. * @return {number}
    4. */
    5. var longestConsecutive = function(nums) {
    6.   const len = nums.length
    7.   if(!len){
    8.       return 0
    9.   }
    10.   nums.sort((a, b) => a - b)
    12.   let maxLen = 1, curLen = 1
    14.   for(let i = 1; i < len; i++){
    15.       if(nums[i] - nums[i - 1] === 1){
    16.           curLen++
    17.       }else if(nums[i] === nums[i - 1]){
    18.           continue
    19.       }else{            
    20.           curLen = 1
    21.       }
    22.       if (curLen > maxLen) {
    23.           maxLen = curLen
    24.       }
    25.   }
    26.   return maxLen
    27. };

    4. 提交结果

    image.png