题目
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为O(n)。
示例
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
题目分析
集合法
题目要求我们的时间复杂度是O(n)，由于set中查找的时间复杂度是常数级，所以我们采用集合法解决。大致思路是：遍历原数组nums，在集合中寻找nums[i] - 1，如果存在，则说明nums[i]不是起点；若不存在，则说明nums[i]是一个起点，在集合中不断寻找当前数字自增1，直到找不到为之，更新长度。
set<int> s(nums.begin(), nums.end());
for (auto n : nums) {
int temp = 1;
if (s.count(n - 1)) continue;
else {
while ( s.count(n + 1) ) {
n++;
temp++;
}
res = temp > res ? temp : res;
}
}
题目解答
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.size() == 0) return 0;
set<int> s(nums.begin(), nums.end());
int maxlen = 1;
for (auto n : nums) {
int temp = 1;
if (s.count(n - 1)) {
continue;
}else {
int t = n;
while (s.count(t + 1)) {
temp++;
t++;
}
maxlen = temp > maxlen ? temp : maxlen;
}
}
return maxlen;
}
};
