https://leetcode.com/problems/longest-consecutive-sequence/
这个问题做到O(n)还是需要动一番脑筋。注意：不是找最长递增子序列。
思路：注意到每个元素必属于一个连续递增序列，而且不会出现重复，有点并查集的感觉。所以我们只要找到每个元素所属的连续序列，取最长的即可。由于有的元素属于同一个连续序列，考察完一个连续序列后把其中所有的元素删除可以避免重复考察。
算法：先把数组中所有元素放到一个Hash Set中，然后遍历数组每个元素，考察该元素所在的最长连续序列（看比该元素小和大的元素是否也在set中，即连续减1/加1能延伸到多远，考察一个就删除一个），记录最长的序列长度即可。
在hash set中，每个元素都被插入和删除一次，平摊复杂度是O(n)。
class Solution { public:int longestConsecutive(vector<int> &nums) {if (nums.empty()) return 0;unordered_set<int> myset(nums.begin(), nums.end());int ret = 1;for (auto num : nums) {if (myset.empty()) break;if (myset.count(num) == 0) continue;int len = 1;// lowerint lower = num - 1;while (myset.count(lower) == 1) {myset.erase(lower);len++; lower--;}// higherint higher = num + 1;while (myset.count(higher) == 1) {myset.erase(higher);len++; higher++;}myset.erase(num);ret = max(ret, len);}return ret;} };