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.

 

算法：这个题第一眼看到想到的是动态规划，先排序，然后用动态规划，求得每个点的连续长度取最大值，这种方法肯定不行，代码也没有通过 提示：required from here

后来在网上搜到一个方法，哈希表，把数组存到哈希表，然后遍历数组，分别在哈希表中向前向后找连续数字，并把找到的关键字从哈希表中删除，因为该值已经没有用了，记录连续区域的长度，与前面记录的最大长度比较。（时间复杂度是O(n)）代码如下：

 

1 class Solution { 2 public: 3     set
     
        m; 4     int longestConsecutive(vector
      
        &num) { 5         int len=num.size(); 6  7         int ma=0; 8         for(int i=0;i
       

::iterator ite;23 while((ite=m.find(nu))!=m.end())24 {25 m.erase(ite);26 ma++;27 if(asc) nu--; else nu++;28 }29 return ma;30 }31 32 };