128. 最长连续序列

发表于 | 分类于

说明

给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:

1
2
3
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路

  1. 遍历nums,放入set里
  2. 遍历set,判断当前数是否是最小值(是否存在小于nu-1)
  3. 如果当前数是最小的，从当前数num开始循环判断是否存在num+1等

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let numSet = new Set();
    let continuesAns = 0;
    for(let k of nums){
        numSet.add(k);
    }
    for(let num of numSet){
        //如果false,说明当前数不是最小的，跳过
        if(!numSet.has(num-1)){
            let n = num;
            let tmp = 1;
            while(numSet.has(n+1)){
                n++;
                tmp++;
            }
            continuesAns = Math.max(continuesAns,tmp);
        }
    }
    return continuesAns;
};