Longest Consecutive Sequence

题目地址：
https://leetcode.com/problems/longest-consecutive-sequence/#/description

题目：

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.

解题思路：
这道题需要用到map，首先map中如果没有的话，就分别从两边找一个单位，如果map有，那么分别命名为leftLen和rightLen，然后相加再加1作为自己的len，之后更行rst和map的三个pair，分别为nums[i], nums[i] - leftLen和nums[i] + rightLen。这道题的tricky之处在于：每个map里面的key对应的length都是包括该点的最长length，不管是从length中间的点还是两边的点。

代码：

public int longestConsecutive(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int rst = 0;
    for(int i = 0; i <= nums.length - 1; i++){
        if(!map.containsKey(nums[i])){
            int leftLen = map.get(nums[i] - 1) == null ? 0 : map.get(nums[i] - 1);
            int rightLen = map.get(nums[i] + 1) == null ? 0 : map.get(nums[i] + 1);
            int len = leftLen + rightLen + 1;
            rst = Math.max(rst, len);
            map.put(nums[i], len);
            map.put(nums[i] - leftLen, len);
            map.put(nums[i] + rightLen, len);
        }
    }
    return rst;
}