【LC128】最长连续序列，哈希

要求O(n)的时间复杂度是本题难点，如果排序或使用二叉平衡树、红黑树（C++ map,set）来解决，复杂度是O(nlogn)，只能采用哈希。
C++中的哈希是unordered_set和unordered_map，本题用unordered_set。
unordered_set是没有自动排序的，如果一个个遍历，寻找连续的元素，复杂度会成n方，这里采用一个巧妙的方法：
对于x1,x2,x3…,xn，最长的连续序列，应该是从x1开始，x1满足一个x2-xn不满足的条件，就是x1在set中没有前驱元素x1-1
这样就只会遍历n次，单次遍历复杂度为1，就有了On的算法

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> numSet;for(auto num : nums){numSet.insert(num);}int left = 0, right = 0, ans = 0;if (nums.size() > 0) ans=1;for(auto num : numSet){if (numSet.count(num-1) == 0){left = num-1;right = num;while(numSet.count(num+1)){right++;num++;}ans = max(ans, right-left);}}return ans;}
};