LeetCode----Longest Consecutive Sequence

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.

思路 1：最简单的方法是 先排序， 然后扫描一遍数组。。复杂度是 O(nlgn) 不符合要求

思路 2：用 hash表 记录 n 个元素。

然后扫描数组，如果当前元素在 Hash 表中存在，求其所在的最大连续区间（向左，向右延伸）在搜索的过程中 删除 Hash 表中对应的元素。

如果当前元素在 Hash 表中不存在，这个元素要么不存在，要么被 删除了， 跳过。

class Solution {
public:
    int longestConsecutive(vector
  
    &num) {
        unordered_set
   
     visited(num.begin(), num.end()); int len(0), longest(0); for(vector
    
     ::iterator it = num.begin(); it != num.end(); ++it){ if(visited.find(*it) == visited.end()) continue; len = 0; //向后延伸 for(int i=*it; visited.find(i)!=visited.end(); ++i, ++len) visited.erase(i); //向前延伸 for(int i=*it-1; visited.find(i)!=visited.end(); --i, ++len) visited.erase(i); longest = max(longest, len); } return longest; } };