【python/Hard/128】 Longest Consecutive Sequence

题目

这里写图片描述

基本思路

使用一个哈希表(在Python中是字典dict数据类型)。
dict中的映射关系是{num: False for num in nums},这个表示nums中的x元素没有被访问过,如果被访问过,则为True。
如果x没有被访问过,检查x+1,x+2…,x-1,x-2是否在dict中,如果在dict中,就可以计数。
最后可以求得最大长度。

实现代码

class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {num: False for num in nums}
        maxLen = 0
        for i in dic:
            if dic[i] == False:
                cur,rightLen = i+1,0
                while cur in dic:
                    dic[cur] = True
                    rightLen += 1
                    cur += 1
                cur,leftLen = i-1,0
                while cur in dic:
                    dic[cur] = True
                    leftLen += 1
                    cur -= 1
                maxLen = max(maxLen,leftLen+1+rightLen)
        return maxLen
                
                
原文链接:加载失败,请重新获取