128. 最长连续序列

给定一个无序数组，要求最长连续序列，要求O(n)解决

第一种：O(nlogn)

        样例比较水可以勉强通过，使用set去重加排序，遍历去重后的数组，如果当前元素是上一个元素+1，那么最长序列长度加一

class Solution {
public:int longestConsecutive(vector<int>& nums) {if(nums.size()==0) return 0;set<int> s;for(auto it:nums) s.insert(it);nums.clear();for(auto it:s) nums.push_back(it);vector<int> dp(nums.size(),1);int ans = 1;for (int i = 1;i <nums.size();i++) {if (nums[i] == nums[i - 1] + 1) dp[i] = dp[i - 1] + 1;ans = max(ans,dp[i]);}return ans;}
};

第二种：

        想要达到O(n)时间复杂度是不能用排序的，因为排序的时间复杂度是O(nlogn)，我们可以使用哈希集合对是否存在某个元素进行O(1)判断，如果x-1存在，那么不以x为序列开头，因为x-1可以得到的最长连续序列一定比x长，例如3 1 2 4，以3开头最长获得2，2开头最长获得3。

        具体思路：将nums转换为哈希集合，对x-1进行存在判断，如果存在，继续找x-1-1是否存在，如果不存在，那么他就是以x开头的最长连续序列，之后对x+1，x+1+1，进行存在判断即可

        代码：

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> st(nums.begin(),nums.end());int ans = 0;for (auto x:st) {if (st.contains(x - 1)) continue;int y = x + 1;while (st.contains(y)) {y++;}ans = max(ans,y - x);//y-1 到 x 有y - x个数}return ans;}
};

时间复杂度：O(n),n为nums的长度，也可以是nums中不重复元素的个数，在二重循环中，每个元素最多被遍历两次O(2*n) = O(n)，一次在遍历集合，一次在遍历x+1