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.
想法一：
用01数组代表该数字是否存在序列中，化归为：一个01序列中，最长连续1的问题。
小数据上可以，但是大数据测试上遇到了问题，当数据跨度很大，比如INT_MIN~INT_MAX时，空间复杂度太高。
想法二：
用map代替数组实现上面的想法，可以解决空间复杂度问题。
但是在计算最长连续1的过程中发现新的问题，遍历INT_MIN~INT_MAX的时间复杂度太高。
解法：
对num数组中的元素进行左右最大扩展计数，代替全范围的遍历计数。
class Solution {
public:
int longestConsecutive(vector<int> &num) {
int ret = ;
unordered_map<int, bool> m;
for(int i = ; i < num.size(); i ++)
m[num[i]] = false;
for(int i = ; i < num.size(); i ++)
{
if(m[num[i]] == false)
{
int cur = ;
int left = num[i]-;
while(m.find(left) != m.end() && m[left] == false && left >= INT_MIN)
{
m[left] = true;
cur ++;
left --;
}
int right = num[i]+;
while(m.find(right) != m.end() && m[right] == false && right <= INT_MAX)
{
m[right] = true;
cur ++;
right ++;
}
ret = max(ret, cur);
}
}
return ret;
}
};