class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dictionary = {}
maxLength = 1
for n in nums:
length = 1
left = 0
right = 0
if n in dictionary:
continue
dictionary[n] = 1
if n  1 in dictionary:
length += dictionary[n  1]
left = dictionary[n  1]
if n + 1 in dictionary:
length += dictionary[n + 1]
right = dictionary[n + 1]
dictionary[n  left] = length
dictionary[n + right] = length
if maxLength < length:
maxLength = length
return maxLength
My simple answer in Python. Real O(n).


Maybe i cann't describle it correctly and resonably
dictionary = {} dictionary[x] = y means : the length 'y' of the longest consecutive sequence which contains the current element 'x'.
every time in the for circle， we find an element which has not been visited . Then we calculate and update the maxlenth the element can constructe.

@weiheng4
It's the complexity of a single dict lookup, which is on average O(1) and at worst O(n). .list() will always be O(n). wiki.python.org/moin/TimeComplexity