128. 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.

思路1：用HashMap记录每个片段的长度。详细点这里

public class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int n:nums){
            if (!map.containsKey(n)){
                int left = (map.containsKey(n-1)) ? map.get(n-1):0;
                int right = (map.containsKey(n+1)) ? map.get(n+1):0;
                // keep track of the max length 
                int sum = left+right+1;
                map.put(n,sum);

                // keep track of the max length 
                res = Math.max(res,sum);

                // extend the length to the boundary(s)
                // of the sequence
                // will do nothing if n has no neighbors
                map.put(n-left,sum);
                map.put(n+right,sum);
            }
        }
        return res;
    }
}

思路2: 用Hashset塞满再做删减

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums==null||nums.length==0) return 0;
        int max = Integer.MIN_VALUE;

        HashSet<Integer> set = new HashSet<Integer>();
        for (int i=0; i<nums.length; i++){
            set.add(nums[i]);
        }

        for (int i=0; i<nums.length; i++){
            int count = 1;
            // look left
            int num = nums[i];
            while (set.contains(--num)){
                count++;
                set.remove(num);
            }

            // look right
            num = nums[i];
            while (set.contains(++num)){
                count++;
                set.remove(num);
            }

            max = Math.max(count,max);
        }
        return max;
    }
}