哈希算法题目：最长连续序列 题目描述 给定一个未排序的整数数组 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 解题过程 步骤1：理解问题核心 题目要求找出最长的连续数字序列。这里的“连续”指的是数字值本身连续，比如1,2,3,4...，而不是指这些数字在原始数组中的位置连续。关键约束是要求算法时间复杂度为O(n)，这排除了先排序（通常O(n log n)）再查找的简单方法。 步骤2：初步思路分析 一个直观想法是使用哈希集合（HashSet）来存储所有数字，利用其O(1)的查找特性。核心思路是：对于一个连续序列，如果我们能快速找到它的起点（即序列中没有比它小1的数字），然后从这个起点开始逐个向后（+1）查找，就能确定整个序列的长度。 步骤3：算法详细步骤 构建哈希集合 ：首先，将数组中的所有数字存入一个哈希集合（称为 numSet ）。这一步的目的是为了后续能够以O(1)的时间判断某个数字是否存在。 寻找序列起点并扩展 ：遍历哈希集合中的每个数字（ num ）。 判断是否为起点 ：检查 num - 1 这个数字是否存在于集合中。如果不存在，说明 num 有可能是一个连续序列的起点。 扩展序列 ：如果 num 是起点，我们就初始化一个计数器 currentStreak = 1 ，然后不断地检查 num + 1 ， num + 2 ， num + 3 ...是否存在于集合中。每存在一个，计数器 currentStreak 就加1。 更新最长序列 ：在扩展每个序列后，将 currentStreak 与记录的最大长度 longestStreak 进行比较，更新最大值。 返回结果 ：遍历结束后， longestStreak 就是答案。 为什么这个算法是O(n)？ 虽然代码中有一个嵌套的while循环，但每个数字最多只会被内层循环访问两次（一次是作为某个序列的起点被扩展，另一次是当它是某个长序列的中间部分时，因为 num-1 存在，它根本不会进入内层循环）。因此，总的时间复杂度是O(n)。 步骤4：举例说明 以示例1 nums = [100,4,200,1,3,2] 为例： 构建集合： numSet = {100, 4, 200, 1, 3, 2} 。 遍历集合： 数字100：检查99是否存在？不存在。所以100是起点。开始扩展：101不存在。序列长度为1。 数字4：检查3是否存在？存在。所以4不是起点，跳过。 数字200：检查199不存在？不存在。是起点。扩展：201不存在。序列长度为1。 数字1：检查0不存在？不存在。是起点。开始扩展：2存在，计数器变2；3存在，计数器变3；4存在，计数器变4；5不存在，停止。序列长度为4。 数字3：检查2存在？存在。不是起点，跳过。 数字2：检查1存在？存在。不是起点，跳过。 得到的最长序列长度是4。 步骤5：关键点与边界情况 关键点 ：通过判断 num-1 是否存在来避免重复计算，这是保证O(n)时间复杂度的精髓。 边界情况 ： 空数组：直接返回0。 数组中有重复元素：使用集合会自动去重，不影响结果正确性。例如 [0,0] ，集合为 {0} ，最长序列是1。