Longest Consecutive Sequence(Hard)

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.

大意：对一个无序的数组，找出其中最长的连续子序列

O(n)的复杂度，目前只找到了使用hash来解决的方案，add, remove, contains 等方法的复杂度都是 O(1)，因此两次遍历的操作复杂度为 O(n)。

public int longestConsecutive(int[] num) {
        Set<Integer> set = new HashSet<Integer>();
        int max = 1;
        for (int e : num)
            set.add(e);

        for (int e : num) {
            int left = e - 1;
            int right = e + 1;
            int count = 1;
            while (set.contains(left)) {
                count++;
                set.remove(left);
                left--;
            }

            while (set.contains(right)) {
                count++;
                set.remove(right);
                right++;
            }
            max = Math.max(count, max);
        }
        return max;
}