一、数据的预处理
要找一个数是不是在数组中，不可能用遍历的方法实现，这样时间复杂度就超过O(n)了。而要降低时间复杂度，一个经典的方案就是空间换时间。用增加空间复杂度的方法来换取时间复杂度的降低。所以我们可以先对数组进行一次预处理，生成一份包含数组元素的哈希表。这样在求解某个数字在不在数组时就可以得到O(1)的时间复杂度。
二、union find 原理和优化
参考自：http://blog.csdn.net/dm_vincent/article/details/7655764
场景
(1) 连通图
主要思想
- 怎么表示节点之间的联通关系？
find ：确定元素属于哪个子集、是否同一子集？ - 如何将节点以更好的方式组织起来？可否牵一发动全身？
union： 将两个元素合并成一个子集。
方案：
- 什么样子的数据结构能够将一些节点给组织起来？（链表，图，树……）
- 哪种结构对于查找和修改的效率最高？--> 树
Find：根据其父节点的引用向根行进直到到底树根。
Union：将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。
- 可以不改变底层结构吗？ --> parent link
如果在不改变底层结构的情况下，即不改变使用数组的表示方法，可以使用 parent link模型，这样，合并两棵树的操作就是:
id[pRoot] = qRoot或者是id[qRoot] = pRoot
优化方法：
1. weighted union（小树合并到大树）
但是，树这种数据结构容易出现极端情况，因为在建树的过程中，树的最终形态严重依赖于输入数据本身的性质，比如数据是否排序，是否随机分布等等。
比如在输入数据是有序的情况下，构造的BST会退化成一个链表。在我们这个问题中，也是会出现的极端情况的。
解决方法”：总是选择小树和大树合并，合并，即id[pRoot] = qRoot
所以需要一个另外的数组记该点所属的conpoment的大小。
2.压缩查询路径（树的扁平化）
另外的一个问题就是，在向上找根节点的时候，效率不高，
解决方法：在union操作中，在while里面，把 p->father 改成 p->grandpap
三、leetcode 上union find的题目
（1） leetcode 128
-
题目
[200 2 190 100 3 1 4] 找出里面连续的序列：[1, 2, 3, 4] - 思想：找出关系 --> 集合内部：(1,2) (2,3) (3,4)
-
流程
先用一个hashSet保存所有的 id : (100,4,200,1,3,2)
先构造一个数组，放每个数字的朋友，一开始自己是自己的朋友：
relation: [100, 4, 200, 1, 3, 2]
然后依次判断一个 pair关系（100,99），（4,3），（200,199），（1,0），（3,2），（2,1）。
过程如下：
先判断（100,99）: 在hashSet 里面找不到99, continue;
然后判断（4,3）：在hashSet里面可以找到3，所以把 relation 数组进行更新：变成 [100, 4, 200, 1, 4, 2]
判断（200,199）， 没有199，continue；
判断（1,0），没有0，continue;
判断（3,2），有2， relation 数组更新为 [100, 4, 200, 1, 4, 4 ]
判断（2,1），有1， relation 数组更新为 [100, 4, 200, 4, 4, 4 ]
所以可以判断有3个component
具体实现
1. 怎么记录size？
2. 如果某些数字特别大，怎么存放索引？
解决方法
HashMap
注意的细节
(1) 给出的数组可能会有重复
(2) 怎么表征“找不到”， 注意，数组中可能有负数
(3) HashMap 的更新要怎么更新
(4) 更新的时候，是在root point那里更新，而不是就地更新
