Leetcode128.最长连续序列

题目描述
给定一个未排序的整数数组 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

示例 3：

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

注意重复的数字不会打断最长序列。

解题思路：将原数组从小到大排序，遍历数组，遇到不连续的情况，保存之前连续的数组及其长度，然后从不连续的字母继续开始遍历。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
   
    if(nums.length<2){
   
        return nums.length
    }
    function sortFn(value1,value2){
   
        return value1-value2
    }
    nums.sort(sortFn)
    let map=new Map()
    let i=0
    let key=i.toString()
    map.set(key,[nums[i]])
    while(i<nums.length-1){
   
        let list=map.get(key)?map.get(key):new Array()
        if(nums[i]+1===nums[i+1]){
   
            list.push(nums[i+1])
            map.set(key,list)
        }
        else if(nums[i]===nums[i+1]){
   }
        else{
   
            key=(i+1).toString()
            map.set(key,[nums[i+1]])
        }
        i++
    }
    let arr=Array.from(map.values())
    let len=0
    let ind=-1
    arr.forEach((item,index)=>{
   
        if(item.length>len){
   
            len=item.length
            ind=index
        }
    })
    return len
};

一开始想说将每个连续的数组都保存至哈希表中，后来看题干发现只要求最长的长度就行，所以用变量保存长度更加便捷。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
   
    if(nums.length<2){
   
        return nums.length
    }
    function sortFn(value1,value2){
   
        return value1-value2
    }
    nums.sort(sortFn)
    let maxLen=0
    let i=0
    let len=1
    while(i<nums.length-1){
   
        if(nums[i]+1===nums[i+1]){
   
            len++
        }
        else if(nums[i]===nums[i+1]){
   }
        else{
   
                len=1

        }
        if(len>maxLen){
   
                maxLen=len
            }
        i++
    }
    
    return maxLen
};

能用for的时候尽量用for，while还是没有for方便~

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
   
    if(nums.length<2){
   
        return nums.length
    }
    function sortFn(value1,value2){
   
        return value1-value2
    }
    nums.sort(sortFn)
    let maxLen=0
    let i=0
    let len=1
    for(let i=0;i<nums.length-1;i++){
   
        if(nums[i]+1===nums[i+1]){
   
            len++
        }
        else if(nums[i]===nums[i+1]){
   }
        else{
   
                len=1

        }
        if(len>maxLen){
   
                maxLen=len
            }
    }
    return maxLen
};