QUESTION:

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4

EXPLANATION:

首先看到要求的就是O(n)的时间复杂度，那么就不能采用多循环的方式，所以想到的思路就是用hashset来记录。
思路：
1.循环数组，用hashset来进行去重
2.再次进行循环，当n-1不存在时，那么可以循环查找n+1是否存在，这样就可以找到一个连续的，同时保证了一个连续只循环一次
3.将连续的结果和result进行比对
4.循环结束返回result

这样的时间复杂度就是第一个for循环n+第二个for循环n*hashset的O(1)查找。最后结果就是O(n)了，同时发现在jdk8中的hashset增加了hash碰撞的红黑树，所以会快很多。

SOLUTION:

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int n : nums) set.add(n);
        int result = 0;
        for(int n:nums){
            if(!set.contains(n-1)){
                int curN = n;
                int tmp = 1;

                while (set.contains(curN+1)){
                    curN++;
                    tmp++;
                }
                result = Math.max(result,tmp);
            }
        }
        return result;
    }
}