128. Longest Consecutive Sequence

1. Description

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

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

3. Solution

• Runtime: 44ms
• 설명
  • 📌답지를 보고 풀게 되었다.
  • Chat GPT로 코드 분석을 했다.
  • 중복을 제거하기 위해 set 사용
  • 리스트의 각 숫자를 순회하여 연속 수열의 시작점 찾기
  • 연속된 숫자의 길이 측정
  • 가장 긴 연속 수열의 길이 갱신

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        set_nums = set(nums)
        longest = 0
 
        for n in set_nums:
            if n - 1 not in set_nums:
                length = 1
 
                while n + length in set_nums:
                    length += 1
 
                longest = max(longest, length)
        
        return longest

4. What I Learned

References

• Write resources that you helped from