Q:

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.

A：使用Map来处理。对cluster来说，最重要的是上界，下界和长度。

对于a[i]，只需要检查a[i]-1，a[i]+1

映射上界下界到区间长度。merge 相邻的cluster时，只需要更新上界和下界对应的区间长度。

//1. The key factors about a cluster is: lowest, highest, and length.//2. Map lowest and highest to length. To merge two neighbor clusters, only need to update it's new lowest and highest, with new length.//3. For every a[i], checking its neighbor a[i]-1 and a[i]+1 is enough.    int longestConsecutive(vector
     
       &num) {        // Start typing your C/C++ solution below        // DO NOT write int main() function                if(num.empty())            return 0;                    int maxlen = 1;            //注意，初始化时1，而不是0                map
      
        hmap;                for(int i=0;i
       
        & hmap,int left,int right)    {        int lower = left-hmap[left]+1;//新区间的下届        int upper = right+hmap[right]-1; //新区间的上届                int len = upper - lower +1;        hmap[lower] = len;        hmap[upper] = len;        return len;    }