最长连续序列（困难）

---

题目叙述：

给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。

示例：

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

解题思路：

方法一：

这个思路比较简单，但不是我本人推荐的一个方式，那就是将所有的元素进行一次排序，然后就从头开始遍历统计，取最大的值，这个方法如果算上排序的时间复杂度是O(nlogn)但是它反而是LeetCode上最快的方式。

代码实现：

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums);
        int max = 1;
        int cur = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) continue;
            if (nums[i] == nums[i-1] + 1) {
                cur++;
            } else {
                cur = 1;
            }
            max = Math.max(max, cur);
        }
        return max;
    }
}

方法二：

这个思路就是按照题意的时间复杂度的来做的，我们将用一个Set的集合将所有的元素都存起来。大家都知道Set的查找效率是O(1)。然后我们遍历Set将如果没有一个比他小1的元素之后，找出以它为起始的连续的序列的长度。时间复杂度为O(n)但是LeetCode运行时间比方法一的时间要长。个人揣测出题人的意思应该是这种类似的方法吧，不然不会被定为困难。

实现代码

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) {
            numSet.add(num);
        }
        int max = 0;
        for (int num : numSet) {
            if (!numSet.contains(num-1)) {
                int currentNum = num;
                int cnt = 1;
                while (numSet.contains(currentNum+1)) {
                    currentNum += 1;
                    cnt += 1;
                }
                max = Math.max(max, cnt);
            }
        }
        return max;
    }
}