Leetcode128. 最长连续序列(HOT100)

链接

第一次错误提交：

class Solution {
public:int longestConsecutive(vector<int>& nums) {int n = nums.size();int res = 0;sort(nums.begin(),nums.end());//第一次错误写作：sort(nums,nums+n);nums是std::vector<int>类型，不能与int相加，这不是普通数组，不能这样写for(int i = 0;i<n;){int j = i+1;int count = 1;while(j<n){if(nums[j]==nums[j-1]){++j;}else if(nums[j]==nums[j-1]+1){count++;j++;}else{ res = max(res,count);break;}}                   i = j;}return res;}
};

错误原因是：我把res的更新放在了while里边，这存在一个问题：只有出现 1 3这种差距超过1时res才会更新，那么如果数组长这样：1 2 3 4 5，我就永远不会更新res了，res永远是0，当j 走过n时跳出去......同理，i = j; 这一句也不应该放在里边，否则i 将很难更新，导致超时。 

第二次正确提交：
 

class Solution {
public:int longestConsecutive(vector<int>& nums) {int n = nums.size();int res = 0;sort(nums.begin(),nums.end());for(int i = 0;i<n;){int j = i+1;int count = 1;while(j<n){if(nums[j]==nums[j-1]){++j;}else if(nums[j]==nums[j-1]+1){count++;j++;}else{ break;}}                   res = max(res,count);i = j;}return res;}
};

使用了unordered_set的方法，正确提交，因为重复元素对于本题没有意义，所以去重刚好满足要求。

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> s;int res =  0;for(const auto&e:nums){s.insert(e);}for(const auto& e:nums){if(s.count(e)&&!s.count(e-1)){s.erase(e);int u = e+1;while(s.count(u)){s.erase(u);++u;}res = max(res,u-e);}}return res;}
};