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.

Constraints

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

Example

Example 1:
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.

Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

접근 방법

직관적으로 생각해보자

이중포문으로 돌면서 숫자 하나씩 잡고 자기보다 +1씩 큰 숫자 구해보자. 근데 제약조건이 10^5라서 이중포문은 Big O(n^2)은 시간초과가 날 거 같음.

단순화해서 생각해보자. (내가 생각해본 접근 방법)

배열을 우선 정렬하고 카운팅할 변수를 하나 선언해보자.

오름 차순 정렬 (n log n)
카운팅 변수 선언 해놓고 (prev_count, curr_count)
연속된 수 라면 카운팅 변수에 + 1
연속하지 않은 수가 나온다면 카운팅 변수 변화는 x
그리고 prev_count와 cur_count를 업데이트하고 비교해가면서 두 개중 높은 수를 리턴.
결과적으로 시간복잡도는 n log n 일듯?

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        num_dict = {}
        for num in nums:
            num_dict[num] = True
        for num in num_dict:
            if num - 1 not in num_dict:
                cnt = 1
                target = num + 1
                while target in num_dict:
                    target += 1
                    cnt += 1
                longest = max (longest,cnt)
        return longest

Greedy Two Sum