数组中最长的连续序列

一、功能概述

LongestConsecutive 方法用于查找整数数组中最长连续序列的长度。通过利用集合结构，该方法能有效找到连续的数字序列。

二、代码实现

public int LongestConsecutive(int[] nums)
{
    HashSet<int> set = new HashSet<int>(nums); // 从输入数组 nums 创建 HashSet<int>，允许 O(1) 的查找时间
    int count = 1; // 初始化计数为 1
    foreach (var item in nums) // 遍历每个元素
    {
        if (!set.Contains(item + 1)) // 检查是否为序列的末尾
        {
            int num = item - 1; // 找到序列开始的元素
            while (set.Contains(num)) // 继续查找
            {
                set.Remove(num); // 移除当前元素
                num--; // 减小数值
                count = Math.Max(count, item - num); // 更新最长连续序列的长度
            }
        }
    }

    return nums.Length > 0 ? count : 0; // 返回最长连续序列长度
}

三、代码详细解释

1. HashSet 初始化

首先，该方法通过输入数组 nums 创建一个 HashSet<int>，允许平均 O(1) 的查找时间。

2. 初始计数

变量 count 被初始化为 1，用于跟踪找到的最长连续序列的长度。

3. 迭代数组

方法遍历数组 nums 中的每个元素。

4. 检查序列结束

对每个元素，检查下一个元素（item + 1）是否不在集合中，以判断当前元素是否为连续序列的末尾。

5. 找到序列的开始

如果当前元素是序列的末尾，方法通过减少元素（item - 1）来寻找序列的开头，直到找到不在集合中的元素。

6. 更新计数

在查找过程中，更新 count 以反映序列的长度。

7. 返回结果

最后，返回找到的最长连续序列的长度，如果数组为空，则返回 0。

四、示例

输入： nums = [100, 6, 200, 5, 7, 8]
输出： 4
解释：最长连续元素序列为 [5, 6, 7, 8]，因此长度为 4。

五、时间复杂度

此方法的时间复杂度为 O(n)，其中 n 是输入数组中的元素数量。通过利用集合，查找和更新操作均能保持高效。