2021-01-31 | 128. 最长连续序列

- 日理万妓 2022-10-31 13:46 149阅读 0赞

### 1. 题目描述 ###

给定一个未排序的整数数组 `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 <= 10`
 *  `-10 <= nums[i] <= 10`

### 2. 解题思路 ###

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

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

**复杂度分析：**

*  时间复杂度：O(nlogn)
 *  空间复杂度：O(n)

### 3. 代码实现 ###

/** * @param {number[]} nums * @return {number} */
    var longestConsecutive = function(nums) { 
        const len = nums.length
        if(!len){ 
            return 0
        }
        nums.sort((a, b) => a - b)
    
        let maxLen = 1, curLen = 1
    
        for(let i = 1; i < len; i++){ 
            if(nums[i] - nums[i - 1] === 1){ 
                curLen++
            }else if(nums[i] === nums[i - 1]){ 
                continue
            }else{             
                curLen = 1
            }
            if (curLen > maxLen) { 
                maxLen = curLen
            }
        }
        return maxLen
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210222232103424.png]

[20210222232103424.png]: /images/20221024/6aa14aecca054ce0a52286ee61ce47cf.png?