最長連續(xù)序列（困難）

題目敘述：

給定一個未排序的整數(shù)數(shù)組，找出最長連續(xù)序列的長度。
要求算法的時間復(fù)雜度為 O(n)。

示例：

輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長連續(xù)序列是 [1, 2, 3, 4]。它的長度為 4。

解題思路：

方法一：

這個思路比較簡單，但不是我本人推薦的一個方式，那就是將所有的元素進行一次排序，然后就從頭開始遍歷統(tǒng)計，取最大的值，這個方法如果算上排序的時間復(fù)雜度是O(nlogn)但是它反而是LeetCode上最快的方式。

代碼實現(xiàn)：

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;
    }
}

方法二：

這個思路就是按照題意的時間復(fù)雜度的來做的，我們將用一個Set的集合將所有的元素都存起來。大家都知道Set的查找效率是O(1)。然后我們遍歷Set將如果沒有一個比他小1的元素之后，找出以它為起始的連續(xù)的序列的長度。時間復(fù)雜度為O(n)但是LeetCode運行時間比方法一的時間要長。個人揣測出題人的意思應(yīng)該是這種類似的方法吧，不然不會被定為困難。

實現(xiàn)代碼

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;
    }
}