题目:
难度:Hard
相关话题:并查集
、数组
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为O(n) 。
示例:
输入:[100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路:
使用hash
来保存每一个数字的连续长度,对于一个未访问过的数字n
,它的连续长度就是它左侧数字(n-1)的长度 + 它右侧数字(n+1)的长度 + 1
。
并且保存当前长度,最后要更新它左侧和右侧的最新连续长度。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
let hash={},max=0
for(let i=0;i<nums.length;i++){
let cur=nums[i]
if(hash[cur]!=null)continue
let left=hash[cur-1]?hash[cur-1]:0
let right=hash[cur+1]?hash[cur+1]:0
let sum=left+right+1
hash[cur]=sum
max=Math.max(max,sum)
hash[cur-left]=sum
hash[cur+right]=sum
}
return max
};
扩展阅读: