题目

************************************************

• 解（哈希）

        VS完整代码

#include<iostream>
#include<vector>
#include<unordered_set>
#include<utility>
#include<algorithm>
using namespace std;
int n, num;int longestConsecutive(vector<int>& nums) {//使用哈希集合去重，遍历nums，对于每一个在集合中查找其及上下连续数字unordered_set<int> nums_set(nums.begin(), nums.end());int len = 0;int maxlen = 0;for (int num : nums) {if (nums_set.find(num)!= nums_set.end()) {nums_set.erase(num);len = 1;int cur = num - 1;while(nums_set.find(cur) != nums_set.end()) {nums_set.erase(cur);cur--;len++;}cur = num + 1;while (nums_set.find(cur) != nums_set.end()) {nums_set.erase(cur);cur++;len++;}maxlen = maxlen > len ? maxlen : len;}return maxlen;}
}int main() {vector<int> nums;cin >> n;for (int i = 0; i < n; i++) {cin >> num;nums.push_back(num);}cout << longestConsecutive(nums) << endl;return 0;}

力扣代码：

class Solution {
public:int longestConsecutive(vector<int>& nums) {// 使用哈希集合去重，遍历nums，对于每一个在集合中查找其及上下连续数字unordered_set<int> nums_set(nums.begin(), nums.end());int maxlen = 0;for (int num : nums) {if (nums_set.find(num) != nums_set.end()) {nums_set.erase(num);int len = 1;int cur = num - 1;while (nums_set.find(cur) != nums_set.end()) {nums_set.erase(cur);cur--;len++;}cur = num + 1;while (nums_set.find(cur) != nums_set.end()) {nums_set.erase(cur);cur++;len++;}maxlen = maxlen > len ? maxlen : len;}}return maxlen;}
};

通过！

复杂度分析：

用的集合unordered_set，这个集合平均的查找、删除等的时间复杂度通常看作O(1)，我们遍历nums相当于O(n)。但是对于每个元素，我们只会进行一次操作，即删除（第一次访问到，第一次作为cur-1被访问到，或者cur+1被访问到）。故至多为O(n)