Question：
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.

int longestConsecutive(int* nums, int numsSize) {
    
}

解法1: O(n) + 无序 -> hash table
具体实现应该学会调用unordered_map

//
//  main.cpp
//  leetcode
//
//  Created by YangKi on 15/11/09.
//  Copyright © 2015年 YangKi. All rights reserved.
//

#include<cstdlib>
#include<iostream>
#include<vector>
#include<unordered_map>//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
using namespace std;


class Solution
{
public:
    int longestConsecutive(vector<int>& nums)
    {
        if( nums.empty()==true ) return 0;
        
        unordered_map<int, bool> used;
        for ( int i: nums ) used[i] = false;
        int longest = 1;
        
        for(int i: nums)
        {
            if (used[i] == true) continue;
            int length=1;
            used[i]=true;
            
            for(int j=i+1; used.find(j)!=used.end(); j++)
            {
                length++;
                used[j]=true;
            }
            
            for(int j=i-1; used.find(j)!=used.end(); j--)
            {
                length++;
                used[j]=true;
            }
            
            
            if(length>longest) longest=length;
        }
        
        return longest;
    }
};

int main()
{
    Solution *s=new Solution();
    vector<int>v={};
    printf("%d\n", s->longestConsecutive(v));
    return 0;
}

解法2:考虑这样一个聚类模型，在一个数轴上有个无数的聚类，每个聚类由一个或多个数字组成，每个聚类的大小由最大元素减去最小元素得到，每次读入一个元素或者会创造一个新聚类，或者会和其左右的两个聚类合并。这个模型由map来实现，其映射的关系是key->length。具体在c++里用unordered_map来实现。

trap1:会有重复的数字
trap2:only modify the length of low and high

//
//  main.cpp
//  leetcode
//
//  Created by YangKi on 15/11/10.
//  Copyright © 2015年 YangKi. All rights reserved.
//

#include<cstdlib>
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;


class Solution
{
public:
    int longestConsecutive(vector<int>& nums)
    {
        int size = nums.size();
        int l=1;
        unordered_map<int, int>map;
        
        for (int i=0; i<size ; i++)
        {
            if(map.find(nums[i])!= map.end()) continue; //trap1:会有重复的数字
            
            // map does not contain nums[size] yet
            map[ nums[i] ]=1;//at least a one element cluster
            
            //have to merge?
            if(map.find( nums[i]-1 )!=map.end())//can merge the left part
            {
                l = max( clusterMerge(map, nums[i]-1, nums[i]), l);
            }
            
            if(map.find( nums[i]+1 )!=map.end())//can merge the right part
            {
                l = max( clusterMerge(map, nums[i], nums[i]+1), l);
            }
        }
        
        return size == 0? 0: l;
    }
    
private:
    int clusterMerge(unordered_map<int , int> &map, int left, int right)// attention:!!!!!!use &
    {
        int low=left-map[left]+1;
        int high=right+map[right]-1;
        int length = high-low+1;
        map[low]=length;//trap2:only modify the length of low and high
        map[high]=length;
        return length;
    }
};

int main()
{
    Solution *s=new Solution();
    vector<int>v={3,2,4,1};
    printf("%d\n", s->longestConsecutive(v));
    return 0;
}