https://www.cnblogs.com/grandyang/p/4276225.html
把数组中所有的数按照值存储到set中,然后在set中找相邻的值以获得这个区间
先把所有值存储在set中,然后减去的方式,这样可以避免重复计算
时间复杂度如果换成set就是n*logn
为什么这个是o(n)
常规的题中经常是right - left + 1,但是这个题目是right - left - 1,因为right、left都经过了while循环,都走到了不符合条件的情况,也就是都多走了一个位置,所以在原始right和left基础上都需要减1,实际上就变成了right -1 - (left - 1)+ 1,最终就是right - left + 1
class Solution { public: int longestConsecutive(vector<int>& nums) { int res = 0; unordered_set<int> s(nums.begin(),nums.end()); for(int i = 0;i < nums.size();i++){ int val = nums[i]; if(!s.count(val)) continue; s.erase(val); int left = val - 1,right = val + 1; while(s.count(left)){ s.erase(left); left--; } while(s.count(right)){ s.erase(right); right++; } res = max(res,right - left - 1); } return res; } };