#128 Longest Consecutive Sequence
Given an unsorted array of integers numbers
, determine the length of the longest sequence where the integers appear consecutively, meaning the numbers follow one another without any gaps.
Input
numbers: number[]
: An array of integers
Notes
Solution should have a time complexity of O(n)
Examples
Input: numbers = [5,1,-4]Output: 1
Explanation: No consecutive numbers exist,
so the longest consecutive sequence is any single number, giving a length of 1
Input: numbers = [1,-1,-1,-4,-5]Output: 2
Explanation: The consecutive sequences are [1], [-1], [-5, -4].
The longest is [-5, -4], with a length of 2
Input: numbers = [1,-1,0,8,11,10,9,9]Output: 4
Explanation: The longest consecutive sequence is 8, 9, 10, 11, with a length of 4
怎麼解
export default function longestConsecutiveNumberSeq(numbers) {
// first one is sort and if next one is not equal with cuurent + 1
// second is a Set and to check if current + 1 exist
let len = numbers.length;
if (len < 2) return 1;
let lookup = new Set(numbers);
let longest = 1
for(let i=0; i<len; i++){
let currentStreak = 1
let currentNum = numbers[i]
while(lookup.has(currentNum + 1)){
currentStreak++
currentNum++
}
longest = Math.max(longest, currentStreak)
}
return longest
Last updated
Was this helpful?