用dictionary, get item的平均时间复杂度为O(1), 可以把key设为list中的数, value用于标记是否访问过。遍历所有的key, 不断找寻其+1和-1得到的值是否在dictionary中, 记下最长的连续序列长度。

class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        dict = {x:False for x in num} # False means not visited
        maxLen = -1
        for i in dict:
            if dict[i] == False:
                curr = i + 1; len1 = 0
                while curr in dict and dict[curr] == False:
                    len1 += 1; dict[curr] = True; curr += 1
                curr = i - 1; len2 = 0
                while curr in dict and dict[curr] == False:
                    len2 += 1; dict[curr] = True; curr -= 1
                maxLen = max(maxLen, 1 + len1 + len2)
        return maxLen