Leetcode-128-Longest Consecutive

这题让我想了好久，实在找不到的算法，看了下解答，果然是出现了超纲的知识点——unordered_set，这个数据结构我之前从没用过，查了一下，是基于hash table实现的，难怪查找操作这么快。 C++ 11中对unordered_set描述大体如下：无序集合容器（unordered_set）是一个存储唯一(unique，即无重复）的关联容器（Associative container），容器中的元素无特别的秩序关系，该容器允许基于值的快速元素检索，同时也支持正向迭代。

有了平均常数时间的查找操作，问题思路就明了很多了，只需要对每个表中的元素查找其相邻元素是否在表中，若在，继续查找此元素的相邻元素，如此便可找到包含此元素的最长序列了，最后取各个序列最大长度即为最后的解。

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_set<int> record(num.begin(),num.end());
        int res = 0;
        for(int n : num){
            if(record.find(n)==record.end()) continue;
            record.erase(n);
            int prev = n-1,next = n+1;
            while(record.find(prev)!=record.end()) record.erase(prev--);
            while(record.find(next)!=record.end()) record.erase(next++);
            res = max(res,next-prev-1);
        }
        return res;
    }
};