給定為排序的整數(shù)數(shù)組,找到最長連續(xù)元素序列的長度文兢,要求算法時間復(fù)雜度為O(n)
使用map晤斩,鍵為num,值為len姆坚,如果map中存在這個元素澳泵,跳出本次循環(huán),判斷往上往下元素是否在map中有對應(yīng)值兼呵,若有兔辅,則更新之前這個元素的len值腊敲,最后取最大的一個。
時間復(fù)雜度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
};