方法一,排序后遍历,后减前==1,计数, 相等跳过,后减前!=1就保存。
class Solution {
public:int longestConsecutive(vector<int>& nums) {vector<int> ans;int count = 1;sort(nums.begin(),nums.end());if(!nums.size()) return 0;if(nums.size() == 1) return 1;for(int i = 1;i < nums.size();i++){if(nums[i] - nums[i-1] == 1){count++;}else if(nums[i] == nums[i-1]) ans.push_back(count);else{ans.push_back(count);count = 1;}ans.push_back(count);}sort(ans.begin(),ans.end());return ans.back();}
};
方法二:去重后放入哈希表,逐个查找本身-1是否在表中,不在就计数1,在就说明连续,计数+1,当前值继续-1,查看是否在表中,找不到就可以把当前计数保存为当前最大值。
class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> num_set;for (const int& num : nums) {num_set.insert(num);}int longestStreak = 0;for (const int& num : num_set) {if (!num_set.count(num - 1)) {int currentNum = num;int currentStreak = 1;while (num_set.count(currentNum + 1)) {currentNum += 1;currentStreak += 1;}longestStreak = max(longestStreak, currentStreak);}}return longestStreak; }
};