Problem

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Clarification

Your algorithm should run in O(n) complexity.

Example

Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4

思路一(排序)

• 因为数组与顺序无关, 所以可以先进行排序
• 然后一个pointer遍历数组
• 时间复杂度: O(nlogn)
• 空间复杂度: O(1)

思路二(hashset)

• 优化思路:
  • 时间复杂度必为O(n)
  • 所以遍历元素的时候, 要用O(1)时间找出它的consecutive的元素, 因而想到hashset
  • 并且如果集合中有比当前元素大的元素, 那么我们就不往集合中找了. 比如例子中 4 比 3大, 于是跳过3

    public int longestConsecutive(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        Set<Integer> hash = new HashSet<>();
        for (int n: num) {
            hash.add(n);
        }
        int longest = 1;
        for (int n: num) {
            if (hash.contains(n + 1)) {
                continue;
            }
            int temp = 1;
            while (hash.contains(n - 1)) {
                n = n - 1;
                temp++;
            }
            longest = Math.max(longest, temp);
        }
        return longest;
    }