가장 긴 연속 시퀀스

2907 단어 leetcodearrayblind75
정수 nums의 정렬되지 않은 배열이 주어지면 가장 긴 연속 요소 시퀀스의 길이를 반환합니다.

O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.





var longestConsecutive = function (nums) {
    let num_set = new Set(nums);
    let longestStreak = 0;
    for (let num of nums) {
        if (!num_set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;
            while (num_set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }
            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }
    return longestStreak;
}


시간 복잡도 : O(n)

좋은 웹페이지 즐겨찾기