JS_LeetCode03：最长连续序列

img

3.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

Set

它是ES6引入的新数据结构，用于存储一组唯一的值。

本质是用哈希表实现的，用于去重和快速查找。

？和Map的区别

  • 键的类型：没有区别，都是任意类型的值
  • 是否有序：没有区别，都有插入顺序
  • 是否唯一：
    • Set自动去重
    • Map允许相同值不同键

？解题思路

因为要找出最长的连续子序列，首先需要去重，因此使用Set对原数组进行处理。

遍历Set集合中的整数，这里很关键的是需要确认子序列的起点整数（即上一个整数不存在Set里，那么它就是起点整数），如果是起点，则开始使用while遍历是否存在下一个整数，更新当前最大整数和最大子序列长度。

判断整数是否存在于set：使用set.has(num)

如此遍历Set集合，根据起点找到最长的子序列，并更新最大子序列长度，就能得到最后的答案！

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const mySet = new Set(nums)
    let maxLen = 0
    for (const num of mySet) {
        if (!mySet.has(num-1)){
            let curNum = num
            let length = 1
            while (mySet.has(curNum+1)) {
                curNum += 1
                length += 1
            }
            maxLen = Math.max(maxLen,length)
        }
        
    }
    return maxLen

};