[LeetCode | Python] 128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.

longest consecutive sequence를 찾는 문제! O(n) 안으로 풀어야 한다.

주의할 점은 constraints에 nums의 length가 0부터 가능하다는 것

 

 

Hash Set을 이용한 풀이

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0

        for num in numSet:
            if (num - 1) not in numSet:
                length = 1
                while (num + length) in numSet:
                    length += 1
                longest = max(length, longest)
        
        return longest

nums를 set 으로 바꾼다. Hash Set을 이용하면 특정 값이 존재하는지 O(1)의 시간 복잡도로 확인할 수 있다.

if (num - 1) not in numSet 조건문을 통해 연속 시퀀스의 시작점을 찾는다. 시작점에서만 연속된 수열을 계산하므로 중복 계산을 방지할 수 있다.

 

while (num + length) in numSet:

연속된 숫자를 찾을 때 +1씩 증가시키는 대신, 시작점부터 length를 더해가는 방식으로 확인할 수 있다.

 

이렇게 찾은 연속된 시퀀스의 길이를 사용해 최장 길이를 업데이트 한다.