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.

如果对数组先排序，然后遍历排过序的数组便可以得到longest consecutive sequence。不过这样做的时间复杂度是O(nlogn)，不符合要求。如果想时间复杂度是O(n)那么必须用空间换时间。一个常用的空间换时间的是哈希表。这里借鉴leetcode-cpp.pdf里的方法。用一个哈希表used记录一个元素是否被用在consecutive sequence中。对那些没有被用在当前consecutive sequence中的数，我们以其为中心像左右扩张，直至不连续为止，在此过程中记录连续的长度。这个方法有个性质就是，只要我们用了一个在某consecutive sequence中的数，其他在该consecutive sequence中的数也将被用到（因为我们会以某个数为中心，像两侧扩张直至不连续），所以整个算法是two pass(第一个pass建立哈希表，第二个pass找出最长consecutive sequence)，所以时间复杂度是O(n)。代码如下：

 1 class Solution { 2 public: 3     int longestConsecutive(vector<int> &num) { 4         unordered_map<int,bool> used; 5         for(auto i:num)used[i] = false; 6         int longest = 0; 7         for(auto i:num){ 8             if(used[i]) continue; 9             int length = 1;10             used[i] = true;11             for(int j = i+1; used.find(j) != used.end(); j++){12                 used[j] = true;13                 length++;14             }15             for(int j = i-1; used.find(j) != used.end(); j--){16                 used[j] = true;17                 length++;18             }19             if(length > longest) longest = length;20         }21         return longest;22     }23 };