给一个整数数组a[]， 找到其中包含最多连续数的子集，比如给：15, 7, 12, 6, 14, 13, 9, 11，则返回: 5:[11, 12, 13, 14, 15] 。

最简单的方法是sort然后scan一遍，但是要 o(nlgn) ， 有什么 O(n) 的方法吗？

思路：

网上有人用map来做，个人觉得用map的复杂度还是O(nlgn)。并查集可以做到O(n)，但网上一直没有看到完整的代码，所以自己写了一个。

先简单介绍并查集的内容，算法导论和网上都可以找到相应的资料。

并查集是一宗简单的用途广泛的算法和数据结构。并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作。应用很多，比如：求无向图的连通分量个数，实现kruskal算法等。

并查集可以方便地进行以下三种操作：

1、Make(x)：把每一个元素初始化为一个集合，初始化后每一个元素的父节点就是它本身。

2、Find(x)：查找一个元素所在的集合，一个元素所在的集合用这个集合的祖先节点来标识。判断两个元素是否属于同一个集合，只要看他们所在集合的祖先节点是否相同即可。

3、Union(x, y)：合并x、y所在的两个集合，先利用Find()找到两个集合的祖先，若这两个祖先节点不是同一个节点，将其中一个祖先节点指向另一个祖先节点即可。（具体哪个祖先指向哪个祖先可以根据实际情况而定）如图：

并查集的优化：在Find函数中，每次找祖先节点的复杂度是O(n)。当我们经过递归找祖先节点的时候，顺便把这条路径上的所有子孙节点都直接指向祖先，这样下次Find的时候复杂度就变成了O(1)。

回到题目，首先调用Make(x)将每个元素变成一个并查集，然后一次扫描a[i]，查看a[i]-1是否存在，若存在调用Union(a[i], a[i]-1)；查看a[i]+1是否存在，若存在调用Union(a[i]+1, a[i])。在合并的同时更新集合的大小。接下里的问题是怎么判断a[i]-1和a[i]+1是否存在，用哈希可以解决，而且复杂度是O(1)。

该题中并查集的操作都是基于下标的。我们用p[i]表示a[i]的父节点的下标，用len[i]表示以a[i]为根的集合的大小，我们合并的时候总是将较小值集合的祖先指向较大值集合的祖先，这样就只需要记录较大值集合的祖先节点对应的长度。最后扫描数组a[]和len[]，找到最大长度maxLen对应的a[i]。最后的结果就是：a[i]-maxLen+1, a[i]-maxLen+2, ..., a[i]。