香精论坛百度手机seo

这道题最简单的想法就是排序+计数，但是复杂度为O(nlogn)，不符合题意
于是采用哈希表的方法
将所有数字存放在哈希表中，然后开始逐个寻找。
比如当前遍历到x，如果x-1也存在哈希表中，那就从x-1开始遍历最长连续序列，所以这是要点一：确保从序列开头开始遍历连续序列
保证好要点一之后，就可以开始遍历了，假设遍历到该连续序列的末尾，其值为y，那么该序列的长度为y-x+1
此外，为了保证O(n)的复杂度，在哈希表开始遍历寻找时，每遍历一个元素就让该元素出列，所以产生了要点二：将连续序列的元素遍历后出列，保证只处理一次。
例如在示例[200,4,100,1,2,3]中，出列顺序为[200,100,1,2,3,4]

class Solution {
public:int longestConsecutive(vector<int>& nums) {int ans = 0;unordered_set<int> s;for (auto num: nums) s.insert(num);for (auto x: nums) {if (s.count(x) && !s.count(x - 1)) {auto y = x;s.erase(x);while (s.count(y + 1)) {y++;s.erase(y);}ans = max(ans, y - x + 1);}}return ans;}
};