最长连续序列 题目描述 给定一个未排序的整数数组 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 解题过程 这个问题要求找出最长的连续数字序列，虽然数字在序列中必须是连续的，但这些数字在原数组中的位置可以是任意的。最直接的解法是排序后扫描，但排序需要 O(n log n) 时间。题目要求 O(n) 时间复杂度，因此我们需要更巧妙的解法。 步骤1：问题分析 关键观察：一个连续序列可以由其起始数字唯一确定。例如序列 [ 1,2,3,4 ] 的起始数字是 1。如果我们能找到所有可能的序列起始数字，然后从每个起始数字开始向后扩展，就能找到所有连续序列。 如何判断一个数字是否是序列的起始数字？当我们在数组中找不到比该数字小1的数字时，它就是某个序列的起始数字。 步骤2：算法设计 我们可以使用哈希集合来存储所有数字，这样可以实现 O(1) 时间的查找。 算法步骤： 将所有数字放入哈希集合中 遍历集合中的每个数字 对于每个数字，检查它是否是某个序列的起始数字（即集合中不存在 num-1） 如果是起始数字，则从该数字开始向后连续查找（num+1, num+2, ...），统计序列长度 记录遇到的最大序列长度 步骤3：详细实现 让我们用示例 nums = [ 100,4,200,1,3,2 ] 来演示： 创建哈希集合：{100,4,200,1,3,2} 遍历集合中的数字： 数字100：检查99是否存在？不存在 → 100是起始数字 从100开始向后查找：101不存在 序列长度 = 1 数字4：检查3是否存在？存在 → 4不是起始数字，跳过 数字200：检查199不存在？不存在 → 200是起始数字 从200开始向后查找：201不存在 序列长度 = 1 数字1：检查0不存在？不存在 → 1是起始数字 从1开始向后查找：2存在，3存在，4存在，5不存在 序列长度 = 4（1,2,3,4） 数字3：检查2存在？存在 → 不是起始数字，跳过 数字2：检查1存在？存在 → 不是起始数字，跳过 最大序列长度 = 4 步骤4：复杂度分析 时间复杂度：O(n)。虽然看起来有嵌套循环，但每个数字最多被内层循环访问两次（一次作为起始数字检查，一次作为其他序列的一部分），总体是线性时间。 空间复杂度：O(n)。用于存储哈希集合。 步骤5：边界情况处理 空数组：返回0 所有数字相同：序列长度为1 数组中有重复数字：哈希集合会自动去重，不影响结果 这种解法巧妙地利用了哈希集合的快速查找特性，通过识别序列起始点来避免重复计算，从而在O(n)时间内解决问题。