Leetcode-最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 
示例 1：
**输入：**nums = [100,4,200,1,3,2] **输出：**4 **解释：**最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
**输入：**nums = [0,3,7,2,5,8,4,6,0,1] **输出：**9
 
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109

// 大多数排序算法（如快速排序、归并排序等）的平均时间复杂度都是 O(nlogn)。
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(!nums.size())
        {
            return 0;
        }
        std::unordered_set<int> num_set;
        for (const auto &num : nums)
        {
            num_set.insert(num);
        }
        int max_length = 0;
        for (const auto &num : nums)
        {
            if (!num_set.count(num-1))
            {
                int cur_num = num;
                int cur_length = 1;
                while(num_set.count(cur_num+1))
                {
                    ++cur_num;
                    ++cur_length;
                }
                max_length = std::max(cur_length,max_length);
            }
        }
        return max_length;
    }
};

该算法使用哈希表来记录每个数字是否存在，并遍历数组中的每个数字，如果当前数字不是连续序列的起点，则不需要进行处理。如果当前数字是连续序列的起点，则从该数字开始向后遍历，直到找到一个不在哈希表中的数字为止，统计连续序列的长度。同时，使用一个变量 max_length 来记录找到的最长连续序列的长度，并在遍历结束后返回结果。

具体步骤如下：

1. 如果数组为空，则直接返回 0。

2. 使用哈希表来记录每个数字是否存在。

3. 初始化最长连续子序列长度为 0。

4. 遍历数组中的每个数字，如果当前数字不是连续序列的起点，则不需要进行处理。如果当前数字是连续序列的起点，则从该数字开始向后遍历，直到找到一个不在哈希表中的数字为止，统计连续序列的长度，并更新 max_length。

5. 返回 max_length。

该算法的时间复杂度为 O(n)，其中 n 为数组的长度。因为哈希表的查询和插入操作的时间复杂度为 O(1)，所以遍历整个数组的时间复杂度为 O(n)。同时，由于使用了哈希表来记录每个数字是否存在，所以空间复杂度也为 O(n)。