最长连续序列

128. 最长连续序列 (opens new window)

难度困难384收藏分享切换为英文关注反馈

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

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

第一次的想法，但是超时了，因为执行时间的长度由数组的最小值与最大值的区间决定

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let map = {}
    let min = nums[0]
    let max = nums[0]
    for(let i=0;i<nums.length;i++){
        map[nums[i]] = 1
        min = min>nums[i]?nums[i]:min
        max = max<nums[i]?nums[i]:max
    }
    let rs = 0
    let temp = 0
    for(let i=min;i<=max;i++){
        if(map[i]===1){
            temp++
        }else{
            rs = rs>temp?rs:temp
            temp=0
        }
    }
    rs = rs>temp?rs:temp
    return rs
};

更新思路，优化后：

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let map = new Map()
    for(let i=0;i<nums.length;i++){
        map.set(nums[i],1)
    }
    let rs = 0
    for(let i=0;i<nums.length;i++){
        let v = nums[i]
        if(map.get(v)===1){
            let temp = 1
            let a = v
            while(map.has(--a)){
                temp++
                map.set(a,2)
            }
            while(map.has(++v)){
                temp++
                map.set(v,2)
            }
            rs = rs>temp?rs:temp
        }
    }

    return rs
};

别人的思路：【提交记录显示速度比我的快，但是自己复制执行又比我的慢 】

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  let maxLength = 0;
  let map = new Map();
  for (const n of nums) {
    if (!map.has(n)) { // 避免重复更新
      let lLength = (map.get(n - 1) || 0);
      let rLength = (map.get(n + 1) || 0);
      let length = lLength + rLength + 1; // 当前所属连续区域的长度 左侧+右侧+1
      map.set(n, length);
      maxLength = Math.max(maxLength, length);
      map.set(n - lLength, length); // 更新最左侧
      map.set(n + rLength, length); // 更新最右侧
    }
  }
  return maxLength;
};