Longest Consecutive Sequence

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.

这道题目看了答案，思路比较巧妙。首先把所有的元素都放进HashMap，但是对应的value是0。然后对于每一个元素，先尝试往升序需找，如果HashMap有，就把当前长度+1，同时把HashMap里对应的value设为1。这样下次在遍历到这个值且value为1时，说明这个元素已经被遍历过了，不需要再检测。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int longestConsecutive(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i : num) {
            map.put(i, 0);
        }
        
        int max = 0;
        for (int i : num) {
            int curmax = 0;
            int temp = i;
            if (map.get(i) == 1) {
                continue;
            }
            
            while (map.containsKey(temp)) {
                curmax++;
                map.put(temp, 1);
                temp++;
            }
            
            temp = i - 1;
            while (map.containsKey(temp)) {
                curmax++;
                map.put(temp, 1);
                temp--;
            }
            max = Math.max(max, curmax);
        }
        return max;
    }
}