[Coding_Test] Longest_Consecutive_Sequence

Longest Consecutive Sequence

Q. 정렬되어 있지 않은 정수형 배열 nums가 주어졌다. nums 원소를 가지고 만들 수 있는 가장 긴 연속된 수의 개수는 몇개인지 반환하시오

코딩테스트 적용방법!@ 해쉬테이블 활용 => 메모리를 이용해서 시간복잡도를 줄일 때 사용 key in {} 가 핵심

제약조건

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

코드구현

# 중요!~
def longestConsecutive(nums):
    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

print(longestConsecutive([6,7,100, 5, 4, 4]))

참조 : 개발남노씨 코딩테스트