Leetcode 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.

정렬되지 않은 정수 배열이 주어졌을때,
이들로 이룰수 있는 가장 긴 연속하는 수열의 길이를 구하세요
O(n) 시간 복잡도 안에 해결해야 합니다.

예시

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: 가장 긴 연속 수열은 [1, 2, 3, 4] 로 길이는 4이다.

제한

• $0 <= nums.length <= 10^5$
• $-10^9 <= nums[i] <= 10^9$

풀이

1. 먼저 모든 배열의 값을 set에 넣는다.
   • set에 집어 넣음으로서 O(1) 안에 찾아낼수 있다.
2. dict[int, int] 타입의 딕셔너리를 만든다.
3. 배열에서 숫자를 하나하나 꺼내서 s에 없으면 continue, s가 비어있으면 break
4. streak의 기본값을 1로 정하고, 해당 숫자보다 1 작은것이 s에 있으면 streak을 1 늘려준다.
5. 만약 s에 없으면서 ( 이전에 배열 길이를 구했거나 없는 수 ) d에 있으면 그 값을 이용
6. 만약 그도 아니라면 그냥 break

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        if len(nums) == 0: return 0
        
        s: set[int] = set()
        d: dict[int, int] = {}
        
        large = -999999
        
        for num in nums:
            s.add(num)
            
        for num in nums:
            if num not in s: continue
            if len(s) == 0: break
            streak = 1
            s.remove(num)
            for i in range(num - 1, -9999999999, -1):
                if i in s:
                    s.remove(i)
                    streak += 1
                    continue
                elif i in d:
                    streak += d[i]
                break
            d[num] = streak
            large = max(large, d[num])
        
        return large