题目描述
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
题目解析
乍一看，我们能马上想到的方法，就是先进行一次排序，再查找，可是就算我们常用的快速排序也有的复杂度，不合题意，所以这道题我们不能直接用排序。
这时，我们可以牺牲一些空间，来降低时间复杂度。
解法：哈希表
将无序变为有序，并不一定需要直接排序，我们可以用哈希表来“曲线救国”。虽然题目给出的序列是无序的，但是哈希表可以非常高效地访问无序序列。
我们可以建立一个无序哈希表unordered_map<int, bool> visited,哈希表的键对应数组的索引，其值表示数组中的元素是否被访问过。
对于每个元素，我们可以以该元素为中心，分别向左、向右查找连续元素，直到不连续为止，记录这个序列的长度，直到找出最大长度。
遍历每个元素，再以每个元素为中心再次进行迭代，似乎，这是一个的算法呀？
别担心！在遍历每个中心元素时，我们会把标记为true的元素跳过，因为，在这个题目的条件下，一个元素只能属于一个连续序列 ，所以我们无需再关心被访问过的中心元素，它一定会被某一个连续序列所包含。我们的算法，仍然属于级别。
代码：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, bool> visited;
for(auto i : nums)
visited[i] = false;
int maxLen = 0;
for(auto i : nums){
if(visited[i])continue;//如果这个元素被访问过，那么他一定就不再属于另外一个连续序列，直接跳过
int len = 1;//当前序列的长度
visited[i] = true;
for(int j = i + 1; visited.find(j) != visited.end(); ++j){
visited[j] = true;
len++;
}
for(int j = i - 1; visited.find(j) != visited.end(); --j){
visited[j] = true;
len++;
}
maxLen = max(maxLen, len);
}
return maxLen;
}
};
复杂度分析
时间复杂度：，请仔细思考上面的解题思路
空间复杂度：，因为引入了一个哈希表
