leetcode128.最长连续序列(Leetcode128. Longest continuous sequence)

leetcode128.最长连续序列

题目

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

用例

输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

求解

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let res = 0
    //创建哈希表
    let hash = new Object()
    for(let i=0;i<nums.length;i++){
        if(!hash[nums[i]]){
            let left_length = hash[nums[i]-1] || 0 
            let right_length = hash[nums[i]+1] || 0
            let new_length = left_length+right_length+1
            hash[nums[i]]=new_length
            res = Math.max(new_length,res)
            hash[nums[i]-left_length]=new_length
            hash[nums[i]+right_length]=new_length
        }
    }
    return res
};
————————

leetcode128.最长连续序列

subject

Given an unordered integer array nums, find the length of the longest sequence of consecutive numbers (sequence elements are not required to be continuous in the original array).

Please design and implement an algorithm with time complexity O (n) to solve this problem.

Use case

输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

solve

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let res = 0
    //创建哈希表
    let hash = new Object()
    for(let i=0;i<nums.length;i++){
        if(!hash[nums[i]]){
            let left_length = hash[nums[i]-1] || 0 
            let right_length = hash[nums[i]+1] || 0
            let new_length = left_length+right_length+1
            hash[nums[i]]=new_length
            res = Math.max(new_length,res)
            hash[nums[i]-left_length]=new_length
            hash[nums[i]+right_length]=new_length
        }
    }
    return res
};