从零开始的LeetCode刷题日记：128. 最长连续序列

一.相关链接

题目链接：128. 最长连续序列

二.心得体会

       这道题要求时间复杂度是O(n），这就告诉我们不能用排序的方法来做。

       如果这道题用排序的方法，那么就比较简单，只需要在排序之后便利整个数组，当找到有比当前索引元素值小1的数则插入<nums[i], iter->second + 1>。否则插入<nums[i], 1>。

       不使用排序的方法需要先对vector进行去重，然后选择性地对数组中元素进行遍历统计：只有当没有前置元素的时候，才进行向后遍历，统计连续序列长度。

三.代码

1）使用排序的代码：

class Solution {
public:int longestConsecutive(vector<int>& nums) {sort(nums.begin(), nums.end());unordered_map<int,int> m;for(int i : nums) {auto iter = m.find(i - 1);if(iter!=m.end()) {m.insert(pair<int,int>(i, iter->second + 1));}else m.insert(pair<int,int>(i, 1));}int ans = 0;for(int i : nums) {if(m[i] > ans) ans = m[i];}return ans;}
};

2）不使用排序：

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> num_set;//去重for(const int& num : nums) {num_set.insert(num);}int ans = 0;for(const int& num : num_set) {if(!num_set.count(num - 1)) {int tem_ans = 1;int tem_num = num + 1;while(num_set.count(tem_num)) {tem_ans++;tem_num++;}if(tem_ans > ans) ans = tem_ans;}}return ans;}
};