题目描述
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(N).
代码及注释
class Solution{
public:
int longestConsecutive(vector<int>& nums){
// 使用哈希表来监控每个元素是否被考虑过
// 这样才会防止重复考虑，以达到题目n的复杂度
unordered_map<int,bool> used;
// 初始化哈希表，表示初始时每一个元素都还没考虑
// i是key值，而非索引
for(auto i : nums) used[i] = false;
// 初始最长为0
int longest = 0;
for(auto i : nums){
// 如果该元素被考虑过了，则跳出本轮循环
if(used[i]) continue;
// 否则先设置该元素已经被考虑过
used[i] = true;
int length = 1;
// 以该元素为中心，左右扩张，直到不再连续
// find函数如果找不到元素，返回end
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(length,longest);
}
return longest;
}
};
分析
时间复杂度要求我们不能先对数组排好序。
使用哈希表监控每一个元素是否被使用过，可以大幅度减少算法复杂度。
