给定为排序的整数数组,找到最长连续元素序列的长度,要求算法时间复杂度为O(n)
使用map,键为num,值为len,如果map中存在这个元素,跳出本次循环,判断往上往下元素是否在map中有对应值,若有,则更新之前这个元素的len值,最后取最大的一个。
时间复杂度O(n),faster than 53%
var longestConsecutive = function(nums) {
var map = new Map()
var res = 0
for(var num of nums){
if(map.has(num)) continue
var pre = map.get(num - 1)
var next = map.get(num + 1)
var len = 1
len += pre ? pre : 0
len += next ? next: 0
map.set(num, len)
res = Math.max(res, len)
if(pre) map.set(num - pre, len)
if(next) map.set(num + next, len)
}
return res
};