最长连续序列

1、题目

image-20240211200934381

2、题解

思路：借助hash表

考虑枚举数组中每个不存在前驱数n-1的数n，在哈希表中检查是否存在，不存在即跳过。尝试匹配n+1,n+2,……是否存在，假设最长匹配至n+x,则存在长度为x+1的最长连续序列。

官方题解：

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

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

自我版本：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        # num_set = set(nums)
        nums_dict = {}
        for num in nums:
            nums_dict[num] = 1
        for num in nums_dict.keys():
            if num - 1 not in nums_dict.keys():
                current_num = num
                current_streak = 1

                while current_num + 1 in nums_dict.keys():
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak