leet_128

题目大意：

给定一个乱序的int数组，找出数组里面最长的连续序列。比如： nums=[1,8,2,4,3,100,99,0,-1] 其中[-1,0,1,2,3,4]是最长的连续序列，因此结果为6

要求时间复杂度为O(N)

题解：

抛开时间复杂度的限制，最简单也最容易想到的做法就是，排序+一次线性扫描。 但是排序的复杂度就已经是NlogN，显然还得想别的方法。

考虑一下这样的数据结构，如果有一个集合，它里面存放的是连续的值。由于值是连续的，因此可以用(left, right)的tuple来表示这个集合。

• 判断一个值x是否在集合中只需要判断 left <= x <= right
• 合并两个集合(-5, 4) (2,8) 直接取两边的值就可以得到(-5,8)

可以看到如果保证集合中的值是连续的，那么对集合的操作都是O(1)的。

所以一个直观的解法就是，枚举每个值x，把它放到x-1或者x+1所在的集合，如果x-1和x+1所在集合不存在，那么x自成一个集合。假设x=10，存在集合(1,9) (11,20)，把10放到集合任意一个集合之后，两个独立的集合就可以合并了（一个递归的过程）。最终最大的那个集合就是我们的目标。

由于集合的操作都是O(1)所以这个想法看似是可行的，但是……

已知x，怎么找出x所在的集合呢。大家很容易想到map，尤其是熟悉STL的同学。map有几种不同的实现，红黑树是一种常见的实现方式也是STL内置的实现方式。但是红黑树的操作复杂都都是logN的，因此不满足我们的要求。所以我们只能考虑另一种实现方式——HashTable

HashTable实际上就是预先开辟一段连续内存（假设长度L），然后通过hash算法把key散列化到[0, L)，然后就可以通过下标直接索引到对应的值，复杂度是O(1)。最简单的hash算法就是 idx = abs(key)%L。 但是很显然你会发现，这种hash算法会让-x和x都被hash到同样的下标（所谓的hash碰撞）。因此，通过idx索引到的不能是一个值，而应该是一个链表。如果hash碰撞了，就把这个值插到链表尾部。由于不同的key都可能发生hash碰撞，因此链表的结构应该类似于：

type node struct {
    key int
    data int
    next *node
}

每次查询时，key拿到idx，然后找到对应的链表，依次遍历链表，找到node.key == key的节点。

因此你可以看到，如果发生了严重的hash碰撞，极端情况下hashTable的时间复杂度会退化到O(N)。hash碰撞无法避免，但是可以通过一定的算法使得hash结果尽量分布均匀，但这不是我们的重点了。

本题的实现还有一些额外的优化细节，比如集合(6,7) 和 (2,5)合并之后(2,7)，为了避免大量的更新操作，类似于:

for i in [2..7]:
    hash[i].update(newset)

因此我使用了两层指针，思想类似于操作系统的多级内存页表，一次更新尽量影响更多的节点。

闲话

使用hashTable只是假O(n)，因为hash算法的复杂度是一个常数c，当c >= logN 时，还不如直接排序来得快