题目：
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.
代码：
class Solution {
public:
int longestConsecutive(vector<int> &num) {
// hashmap record if element in num is visited
std::map<int,bool> visited;
for(std::vector<int>::iterator i = num.begin(); i != num.end(); ++i)
{
visited[*i] = false;
}
// search the longest consecutive
unsigned int longest_global = ;
for(std::vector<int>::iterator i = num.begin(); i != num.end(); ++i)
{
if(visited[*i]) continue;
unsigned int longest_local = ;
for(int j = *i+; visited.find(j) != visited.end(); ++j)
{
visited[j] = true;
++longest_local;
}
for(int j = *i-; visited.find(j) != visited.end(); --j)
{
visited[j] = true;
++longest_local;
}
longest_global = std::max(longest_global, longest_local+);
}
return longest_global;
}
};
Tips:
1. 要想O(n), 而且无序，只能结合hashmap
2. 这里需要明确的一个逻辑是，通过hashmap前后访问，可以把包含当前元素的最大连同序列都找出来；而且访问过的元素不用再访问。
=======================================================
第二次过这道题，大体的思路能顺下来，但是疏忽了几个细节。AC代码如下：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int global_longest = 1;
// initialize map
unordered_map<int, bool> visited;
for ( int i=0; i<nums.size(); ++i ) visited[nums[i]]=false;
// go one traversal
for ( int i=0; i<nums.size(); ++i )
{
if ( visited[nums[i]] ) continue;
visited[nums[i]] = true;
int local_longest = 1;
int curr = nums[i]-1;
// search towards smaller direction
while ( visited.find(curr)!=visited.end() )
{
local_longest++;
visited[curr] = true;
curr--;
}
// search towards larger direction
curr = nums[i]+1;
while ( visited.find(curr)!=visited.end() )
{
local_longest++;
visited[curr] = true;
curr++;
}
// update global longest
global_longest = std::max(global_longest, local_longest);
}
return global_longest;
}
};
tips:
1. 根据某个元素往‘前’、‘后’两个方向遍历之前，要先记得把该元素设置为访问过（即，visited[nums[i]] = true;）
2. 第一遍把while循环中的 visited[curr]=true都写成了visited[nums[i]]，这个纯属低级错误，不要再犯
3. 第一遍有一个逻辑上的错误：
"for ( int i=0; i<nums.size() && !visited[nums[i]]; ++i )"
本意是跳过已经访问过的元素。。。但是这么写如果遇到了访问过的元素，就不是跳过了，而是直接退出循环了。这是个思维的陷阱，记下来，下次不要再犯。