给定一个未排序的整数数组 nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
进阶:
你可以设计并实现时间复杂度为
O(n)
的解决方案吗?
示例 1:输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1] 输出:9
提示:0 <= nums.length <= 10
-2 <= nums[i] <= 2 - 1
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_map<int, int> hashMap; unordered_map<int, int> visitedMap; for(int i = 0;i<nums.size();i++){ hashMap[nums[i]]++; } unordered_map<int,int>::iterator it; int res = 0; for(it = hashMap.begin(); it != hashMap.end();it++){ long mid = it->first; int count = 1; cout<<mid<<" "<<count<<endl; if(!visitedMap.count(mid)){ mid--; while(mid >= INT_MIN && hashMap.count(mid)){ count ++; visitedMap[mid] = 1; mid--; } cout<<count<<endl; mid = it->first; mid++; while(mid <= INT_MAX && hashMap.count(mid)){ count ++; visitedMap[mid] = 1; mid++; } cout<<count<<endl; } visitedMap[mid] = 1; res = max(res, count); } return res; } };