输入一个乱序数列，输出其中连续数列的长度，要求算法复杂度为 O(n)

例如：输入 1，3，2，5，9，190 。那么连续数列就是 1，2，3 。输出：3

起始最简单的方法就是：先把数组排好序，然后查找最长连续数列。但是这样一来算法复杂度是: O(nlogn) + O(n) ，是不符合要求的。

要以算法复杂度为O(n)解决问题可以使用 hash map 。

思路：

我们在人工查找的时候思路是这样的： 从第一个数字看起，看到数字 1 ，就去找 0 和 2，发现没有 0 但是有 2，此时最长序列是 2，然后往下找 3 ，然后往下找 4..... , 如果当前数组的最左边和对右边都没有连续的数字了，那么当前最长数列的值就是： 当前数字左边连续数列长度 + 当前数字右边连续数列长度 + 1。

已给出的数组为例：第一个数值 1 左侧连续数列长度为 0 ，右侧连续数列的值有 2 和 3，长度为 2 ，则连续数列的长度 = 0 + 2 + 1 = 3 .....以此类推可以求出最长连续数列的值 。

1、先把所有数据 (nums数组) 都放进map (numsMap)中，以数值为 key，True为value ，去查找有没有当前数值的下一位的时候不去遍历 nums ，而是去 numsMap 的 allKeys 中查找。

2、遍历 nums ，以 left 记录 i 左侧连续数列长度， right 记录 i 右侧连续数列长度 ， leftKey = i - 1 , rightKey = i + 1,  以 leftKey 和 rightKey 为 分别 key 去 numsMap 中查找，如果找到 left += 1 , right += 1 , leftKey -= 1 , rightKey -= 1 将当前键值对从 numsMap 中 pop 出去， 然后继续向下查找，直到 leftKey 和 rightKey 都找不到了 在整个 遍历过程中 maxLength = left + right + 1 。

下面是完成的 python 代码实现：

import sysfor line in sys.stdin:    line = line.strip()    nums = line.split(",")    max_length = 0    # list 中所有的元素作为 map 的key值    numsMap = {}    for i in nums:        i = int(i)        numsMap[i] = True    for i in nums:        i = int(i)        if i not in numsMap.keys():            continue        leftLength = 0        rightLength = 0        leftKey = i - 1        rightKey = i + 1        while leftKey in numsMap.keys():            numsMap.pop(leftKey)            leftKey -= 1            leftLength += 1        while rightKey in numsMap.keys():            numsMap.pop(rightKey)            rightKey += 1            rightLength += 1        max_length = max(max_length, rightLength+leftLength+1)    print (max_length)

还有一种思路就是：numsMap 的key 为 数值， value 为 与当前数值相连的最长数列的长度 。这种思路不做过多讲解了，有兴趣的可以自己研究下。贴出代码：

for i in nums:        i = int(i)        if i in numsMap.keys():            continue        left = 0        right = 0        # i - 1        leftKey = i - 1        # i + i        rightKey = i + 1        # 如果拿到 left 值        if leftKey in numsMap.keys():            left = numsMap[leftKey]        if rightKey in numsMap.keys():            right = numsMap[rightKey]        length = left + right + 1        # 存储到字典        numsMap[i] = length        # 更新与 i 相连的连续序列的最左边和最右边的值        numsMap[i-left] = length        numsMap[i+right] = length        max_length = max(max_length, length)