［抄题］：
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
［思维问题］：
以为要用好几个同一种数据结构来实现：其实不用，只要对同一个数自增、自减就可以了。
［一句话思路］：
求出up的上限，down的下限后作差、减1
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 如果集合中查有此数，则把它删掉。否则会导致溢出
［二刷］：
- down up要一直变化，所以要用到2个while小循环
［三刷］：
［总结］：
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［英文数据结构，为什么不用别的数据结构］：
hashmap：没有k-v的对应关系
array：找一次down就要for循环，写起来太麻烦
linkedlist：找一次down就要head-tail循环，写起来太麻烦
直接用hashset.contains判断存在性，避免了从头到尾地查找
［其他解法］：
［Follow Up］：
［题目变变变］：
public class Solution {
/*
* @param num: A list of integers
* @return: An integer
*/
public int longestConsecutive(int[] num) {
//corner case
if (num == null || num.length == 0) {
return 0;
}
//add
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < num.length; i++) {
set.add(num[i]);
}
//find
int max = 0;
for (int i = 0; i < num.length; i++) {
int down = num[i] - 1;
while (set.contains(down)) {
set.remove(down);
down--;
}
int up = num[i] + 1;
while (set.contains(up)) {
set.remove(up);
up++;
}
max = Math.max(max, up - down - 1);
}
return max;
}
}