[LeetCode][Python] 128. Longest Consecutive Sequence

- 문제 링크: https://leetcode.com/problems/longest-consecutive-sequence/

- 난이도: Medium

 

주어진 숫자 배열에서 가장 긴 연속적인 수열 길이를 구하는 문제다

O(n) 시간복잡도만 가능하기 때문에 정렬은 하지 못하고, 해시를 써야 한다

숫자를 하나 뽑아서, n-1이 있는지 확인하고(있으면 수열의 시작이 아님), 그 다음부터 1씩 올려가며 최대 길이를 재면 된다

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

        for n in numSet:
            if (n-1) in numSet:
                continue

            length = 1
            while (n + length) in numSet:
                length += 1

            longest = max(longest, length)

        return longest