logo设计网站参考今日新闻国际头条新闻

题目描述

法一 哈希表

用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1) 的时间复杂度
每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过

int longestConsecutive(vector<int>& nums){unordered_set<int> set;for(const int& num:nums){set.insert(num);}int res=0;for(const int&num:set){if(!set.count(num-1)){int curnum=num;int curcnt=1;while(set.count(curnum+1)){curnum++;curcnt++; }res = max(res, curcnt);}}return res;}