LeetCode 128. 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.

解析：
给定数组，求最长连续序列。此题目首先考虑先进行排序，排序的复杂度为O(nlogn)，但这里要求O(n)的复杂度，所以不满足要求。
由于序列的元素是无序的，并且限制了复杂度，因此考虑哈希表。
使用一个哈希表unordered_map<int,bool> used记录每个元素是否使用。遍历每个元素，以该元素为中心，往左右扩张，直到不连续为止。used保证每个元素只使用一次，因此整体的时间复杂度还是\(O(n)\)
代码如下：
[cc lang=”C++”]
class Solution {
public:
int longestConsecutive(vector& nums) {
unordered_map<int, bool=””> used;//记录每个元素是否使用
for(auto i: nums) used[i] = false;//初始化
int longest = 0;
for(auto i : nums)
{
if(used[i]) continue;
int length = 1;
used[i] = true;
for(int j = i+1; used.find(j)!=used.end(); ++j)//以当前元素为中心，向右扩展
{
used[j] = true;
++ length;
}
for(int j=i-1;used.find(j) !=used.end(); –j)//以当前元素为中心，向左扩展
{
used[j] = true;
++ length;
}
longest = max(longest, length);//记录最大值
}
return longest;
}
};
[/cc]</int,></int,bool>