高校校园网站建设与运行,2022中国企业排行榜,阿里巴巴做网站分录,装修案例朋友圈文案这道题最简单的想法就是排序计数#xff0c;但是复杂度为O(nlogn)#xff0c;不符合题意 于是采用哈希表的方法 将所有数字存放在哈希表中#xff0c;然后开始逐个寻找。 比如当前遍历到x#xff0c;如果x-1也存在哈希表中#xff0c;那就从x-1开始遍历最长连续序列#…这道题最简单的想法就是排序计数但是复杂度为O(nlogn)不符合题意 于是采用哈希表的方法 将所有数字存放在哈希表中然后开始逐个寻找。 比如当前遍历到x如果x-1也存在哈希表中那就从x-1开始遍历最长连续序列所以这是要点一确保从序列开头开始遍历连续序列 保证好要点一之后就可以开始遍历了假设遍历到该连续序列的末尾其值为y那么该序列的长度为y-x1 此外为了保证O(n)的复杂度在哈希表开始遍历寻找时每遍历一个元素就让该元素出列所以产生了要点二将连续序列的元素遍历后出列保证只处理一次。 例如在示例[200,4,100,1,2,3]中出列顺序为[200,100,1,2,3,4]
class Solution {
public:int longestConsecutive(vectorint nums) {int ans 0;unordered_setint 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;}
};
