6/6刷题

1.最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-consecutive-sequence
思路：哈希表

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for(int i=0;i<nums.size();i++)
        {
            num_set.insert(nums[i]);//将数组里的数依次放入哈希表
        }
        int cur=0;
        int res=0;//存储当前长度与最终长度
        for(const int& num : num_set)
        {
            if(!num_set.count(num-1))
            {
                int curNum=num;
                cur=1;//如果该数字x的前一个数字x-1不存在，那么我们就从这个数字开始查找
                while(num_set.count(curNum+1))
                {
                    curNum+=1;
                    cur+=1;//若x+1存在，更新计数
                }
            }
            res=max(cur,res);//如果该数字x的前一个数字x-1存在，说明已经查找过这一波了，直接比较
        }
        return res;
    }
};