 解法与并查集思路)
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于《算法通关手册》中的 0128. 最长连续序列题解系统讲解「在未排序数组中找出数字连续的最长序列长度」这一经典哈希表考题。你将掌握哈希集合去重 「只从序列起点向外延伸」的 O(n) 线性解法、复杂度推导并了解该题标签中的并查集Union Find视角如何与哈希解法殊途同归。本题同时被收录于本仓库的面试 100 题列表与面试 200 题列表属于算法面试的必刷高频题。1. 题目概述1.1 题目大意给定一个未排序的整数数组nums要求找出数字连续的最长序列不要求序列元素在原数组中连续的长度并且要求使用时间复杂度为 $O(n)$ 的算法解决此问题。这里的「连续序列」指的是数值上相邻差值为 1的一组整数与元素在数组中的物理位置无关。例如数组[100, 4, 200, 1, 3, 2]中数字[1, 2, 3, 4]数值上连续尽管它们在原数组中分散在不同位置。1.2 数据范围与示例数据约束题目明确规定$0 \le nums.length \le 10^5$$-10^9 \le nums[i] \le 10^9$示例 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示例 2 中数组含重复元素0去重后连续序列为[0, 1, 2, 3, 4, 5, 6, 7, 8]长度为 9。这个示例很好地提示了必须先去重重复元素不影响序列长度却会干扰遍历计数。值得注意的是同样的题目还以 LCR 119. 最长连续序列 的形式出现在剑指 OfferLCR 系列题解中两道题的核心思路与代码完全一致可互相参考。2. 暴力做法的两种思路与瓶颈在引入 O(n) 解法之前先明确暴力做法的局限性才能理解哈希表优化的价值。2.1 思路 A先排序再扫描对数组排序后连续的数字会聚集在一起只需一趟线性扫描统计相邻差值恰好为 1 的最长段即可。排序本身的时间复杂度下限是 $O(n \log_2 n)$可参考仓库中关于排序算法分类与复杂度的说明快速排序、归并排序等高级排序算法均为 $O(n \log n)$。排序后扫描的复杂度为 $O(n)$但整体仍受限于排序的 $O(n \log n)$。因此排序做法不满足题目 O(n) 的硬性要求。2.2 思路 B枚举每个数作为起点向后暴力匹配枚举数组中的每个数num以其为起点不断尝试匹配num 1、num 2、…… 是否存在。最坏情况下每个起点都需要向后匹配len(nums)次总时间复杂度为 $O(n^2)$。当n接近 $10^5$ 上限时$O(n^2)$ 显然不可接受。3. 思路 1哈希表集合优化解法3.1 核心优化点暴力思路 B 之所以慢是因为它对每一个元素都尝试向外延伸而这些元素中的大多数其实处于某个序列的「中间」或「末尾」从它们出发会重复计算大量前缀。哈希表解法的关键洞察只有两点用集合去重Python 的set底层是哈希表元素的插入与成员查询均为 $O(1)$ 平均时间复杂度哈希表的基本原理可参考仓库中的哈希表专题文档其中详细介绍了哈希函数设计与哈希冲突解决策略。只从序列起点开始延伸一个数num是「某段连续序列的起点」当且仅当num - 1不在集合中。只有满足这个条件的元素才值得向内层while循环延伸从而保证每个序列的每个元素至多被访问一次。3.2 算法步骤将数组存入集合nums_set进行去重用curr_streak维护当前连续序列长度用ans维护最长连续序列长度。遍历集合中的每个元素num若num - 1在集合中说明num不是序列起点直接跳过这是整个算法的效率关键若num - 1不在集合中说明num是某段序列的起点则从num开始依次判断num 1、num 2、…… 是否在集合中并同步累加curr_streak每次内层延伸结束后用ans max(ans, curr_streak)更新全局最长长度。遍历结束后返回ans。3.3 完整代码以下代码严格对应原题解可直接运行class Solution: def longestConsecutive(self, nums: List[int]) - int: ans 0 nums_set set(nums) for num in nums_set: if num - 1 not in nums_set: curr_num num curr_streak 1 while curr_num 1 in nums_set: curr_num 1 curr_streak 1 ans max(ans, curr_streak) return ans代码逐行解读set(nums)一次遍历完成去重同时将原始数组的重复元素剔除避免后续重复统计对应示例 2 中的两个0if num - 1 not in nums_set序列起点的判定条件是 $O(1)$ 复杂度的来源while curr_num 1 in nums_set利用哈希表 $O(1)$ 查询能力逐格向外延伸当前序列ans max(ans, curr_streak)内层循环结束后用当前序列长度刷新全局答案。3.4 正确性验证以示例 1 的nums [100,4,200,1,3,2]手动推演集合为{1, 2, 3, 4, 100, 200}遍历到10 not in set起点成立延伸2 → 3 → 4curr_streak 4ans 4遍历到21 in set跳过遍历到3、4前驱均在集合中跳过遍历到10099 not in set起点成立100 1 101不在集合curr_streak 1ans保持 4遍历到200同理curr_streak 1最终返回4。✅3.5 复杂度分析时间复杂度$O(n)$。将数组存入集合进行去重$O(n)$集合成员查询x in set$O(1)$平均情况哈希表特性遍历集合时所有「非起点」元素只被检查一次前驱后即跳过所有「起点」元素引发的内层while延伸总步数不超过 $n$因为每段连续序列只会从其起点被完整遍历一次序列之间互不重叠。综上整体为 $O(n)$满足题目约束。空间复杂度$O(n)$。需要额外的哈希集合存储所有不重复元素最坏情况下数组元素全部不同集合大小等于数组长度。3.6 注意事项遍历的是nums_set集合而不是原始nums可避免重复元素导致的重复起点判断集合大小写敏感、数值范围可达 $\pm 10^9$因此不能使用计数数组/布尔数组模拟集合空间不可行这正是必须使用哈希表的原因——哈希表只存储实际出现过的元素与数值范围无关。4. 思路 2并查集Union Find视角题目标签中同时标注了「并查集」说明该题存在基于并查集的建模方式。虽然哈希解法更简洁但理解并查集版本有助于打通「连通性」思维并可复用仓库中的并查集专题文档与其基础实现源码。4.1 建模思想将每个数字看作一个节点数值上相邻的两个数差值为 1之间建立一条「连续边」。那么一个连续序列 ⇔ 一张连通分量最长连续序列的长度 ⇔ 节点数最多的那个连通分量的大小。具体步骤可设计为使用哈希表建立「数值 → 下标」的映射把可能很大的数值域压缩到 $[0, n)$ 的索引空间因为 $-10^9 \le nums[i] \le 10^9$直接以数值建数组不可行初始化并查集每个元素自成一个集合遍历每个元素x若x 1存在于映射表中则执行union(x, x1)统计每个连通分量的节点个数取最大值。4.2 与仓库并查集实现对应仓库中的并查集基础实现提供了三个核心接口可直接套用于上述流程find(x)查找元素根节点路径压缩版self.fa[x] self.fa[self.fa[x]]为隔代压缩union(x, y)合并两个集合返回是否发生合并is_connected(x, y)判断两元素是否同属一个集合。需要额外补充的是统计连通分量大小时需要在union成功后维护size数组按大小合并的并查集变体可参考仓库中的 tree_unionFind_UnoinBySize.py每合并一次就将两集合大小相加最后取最大size即可。4.3 两种思路的对比对比维度哈希表思路思路 1并查集思路思路 2时间复杂度$O(n)$去重 起点延伸$O(n \cdot \alpha(n))$接近 $O(n)$含路径压缩与按秩/按大小合并空间复杂度$O(n)$哈希集合$O(n)$fa 数组 哈希映射 size 数组代码量少约 8 行核心逻辑较多需实现并查集类思维视角顺序延伸连通分量合并面试中优先推荐哈希表解法代码短、易解释、无额外类定义负担并查集解法适合在考察「连通性建模」的场合展示或作为复习并查集原理的载体。5. 易混淆题型辨析连续 vs 递增 vs 子序列本仓库题解体系中存在多道名称相近的题目理解差异可避免面试中张冠李戴0128. 最长连续序列本题要求数值连续差值恰为 1元素可无序O(n) 哈希解法LCR 119. 最长连续序列与本题完全同构的 LCR 版本解法相同0300. 最长递增子序列要求严格递增差值至少为 1且保持原数组相对顺序属于单串线性动态规划问题时间复杂度为 $O(n \log n)$ 或 $O(n^2)$详见线性 DP 专题中的练习题目列表。一句话总结本题的「连续」只看数值邻居关系、不看原数组顺序因此集合哈希表天然适配而「子序列」类问题必须保留顺序约束需借助 DP 状态设计。6. 在《算法通关手册》中的定位与延伸学习本题被《算法通关手册》收录于多个关键位置面试 100 题列表 与面试 200 题列表标注为「并查集、数组、哈希表 / 中等」题解总列表 与题目分类列表可在哈希表分类下找到本题及其姊妹题。围绕本题的核心知识点仓库提供了成体系的配套资料哈希表原理哈希表专题系统讲解哈希函数直接定址法、除留余数法、平方取中法、基数转换法等与哈希冲突解决开放地址法、链地址法是理解本题set查询 $O(1)$ 的底层依据并查集原理与实现并查集专题 讲解快速查询基于数组与快速合并基于森林两种实现配合 tree_unionFind.py、tree_unionFind_QuickUnion.py 等源码可深入理解find/union的实现细节与路径压缩优化。总结本题的核心考点可浓缩为三点识别 O(n) 约束排序法 $O(n \log n)$、暴力枚举法 $O(n^2)$ 均不合格必须借助哈希表只从序列起点延伸通过num - 1 not in set判起点保证每个元素至多访问一次是 O(n) 成立的充分条件理解去重的必要性重复元素不影响答案却会破坏计数集合天然解决此问题。掌握哈希表解法后可进一步用并查集视角重新审视本题并借助仓库中的哈希表、并查集专题文档巩固底层原理为后续处理「连通分量」「区间合并」类问题打下基础。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐128. 最长连续序列Longest Consecutive Sequence——哈希表空间换时间的 O(n) 解法详解128. 最长连续序列Longest Consecutive Sequence——哈希表空间换时间的 O n 解法详解 本篇基于 LeetCode 题解仓库文档教程知识库LeetCode 128 最长连续序列从哈希集合到 O(n) 最优解的全解法剖析leetcode 仓库实战LeetCode 128 最长连续序列从哈希集合到 O n 最优解的全解法剖析leetcode 仓库实战 导读 本文围绕 LeetCode 128「Lon示例工程教程LeetCode 128 最长连续序列Longest Consecutive Sequence四种解法全解析从暴力到 O(n) 哈希优化LeetCode 128 最长连续序列Longest Consecutive Sequence四种解法全解析从暴力到 O n 哈希优化 导读 本文以 ar示例工程教程上一篇Hello 算法实战回溯算法框架下的二叉树路径搜索preorder_traversal_iii_template 模板代码全解析下一篇OpenRC 开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 最长连续序列（LeetCode 128）：AlgoNote 详解哈希表 O(n) 解法与并查集思路
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于《算法通关手册》中的 0128. 最长连续序列题解系统讲解「在未排序数组中找出数字连续的最长序列长度」这一经典哈希表考题。你将掌握哈希集合去重 「只从序列起点向外延伸」的 O(n) 线性解法、复杂度推导并了解该题标签中的并查集Union Find视角如何与哈希解法殊途同归。本题同时被收录于本仓库的面试 100 题列表与面试 200 题列表属于算法面试的必刷高频题。1. 题目概述1.1 题目大意给定一个未排序的整数数组nums要求找出数字连续的最长序列不要求序列元素在原数组中连续的长度并且要求使用时间复杂度为 $O(n)$ 的算法解决此问题。这里的「连续序列」指的是数值上相邻差值为 1的一组整数与元素在数组中的物理位置无关。例如数组[100, 4, 200, 1, 3, 2]中数字[1, 2, 3, 4]数值上连续尽管它们在原数组中分散在不同位置。1.2 数据范围与示例数据约束题目明确规定$0 \le nums.length \le 10^5$$-10^9 \le nums[i] \le 10^9$示例 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示例 2 中数组含重复元素0去重后连续序列为[0, 1, 2, 3, 4, 5, 6, 7, 8]长度为 9。这个示例很好地提示了必须先去重重复元素不影响序列长度却会干扰遍历计数。值得注意的是同样的题目还以 LCR 119. 最长连续序列 的形式出现在剑指 OfferLCR 系列题解中两道题的核心思路与代码完全一致可互相参考。2. 暴力做法的两种思路与瓶颈在引入 O(n) 解法之前先明确暴力做法的局限性才能理解哈希表优化的价值。2.1 思路 A先排序再扫描对数组排序后连续的数字会聚集在一起只需一趟线性扫描统计相邻差值恰好为 1 的最长段即可。排序本身的时间复杂度下限是 $O(n \log_2 n)$可参考仓库中关于排序算法分类与复杂度的说明快速排序、归并排序等高级排序算法均为 $O(n \log n)$。排序后扫描的复杂度为 $O(n)$但整体仍受限于排序的 $O(n \log n)$。因此排序做法不满足题目 O(n) 的硬性要求。2.2 思路 B枚举每个数作为起点向后暴力匹配枚举数组中的每个数num以其为起点不断尝试匹配num 1、num 2、…… 是否存在。最坏情况下每个起点都需要向后匹配len(nums)次总时间复杂度为 $O(n^2)$。当n接近 $10^5$ 上限时$O(n^2)$ 显然不可接受。3. 思路 1哈希表集合优化解法3.1 核心优化点暴力思路 B 之所以慢是因为它对每一个元素都尝试向外延伸而这些元素中的大多数其实处于某个序列的「中间」或「末尾」从它们出发会重复计算大量前缀。哈希表解法的关键洞察只有两点用集合去重Python 的set底层是哈希表元素的插入与成员查询均为 $O(1)$ 平均时间复杂度哈希表的基本原理可参考仓库中的哈希表专题文档其中详细介绍了哈希函数设计与哈希冲突解决策略。只从序列起点开始延伸一个数num是「某段连续序列的起点」当且仅当num - 1不在集合中。只有满足这个条件的元素才值得向内层while循环延伸从而保证每个序列的每个元素至多被访问一次。3.2 算法步骤将数组存入集合nums_set进行去重用curr_streak维护当前连续序列长度用ans维护最长连续序列长度。遍历集合中的每个元素num若num - 1在集合中说明num不是序列起点直接跳过这是整个算法的效率关键若num - 1不在集合中说明num是某段序列的起点则从num开始依次判断num 1、num 2、…… 是否在集合中并同步累加curr_streak每次内层延伸结束后用ans max(ans, curr_streak)更新全局最长长度。遍历结束后返回ans。3.3 完整代码以下代码严格对应原题解可直接运行class Solution: def longestConsecutive(self, nums: List[int]) - int: ans 0 nums_set set(nums) for num in nums_set: if num - 1 not in nums_set: curr_num num curr_streak 1 while curr_num 1 in nums_set: curr_num 1 curr_streak 1 ans max(ans, curr_streak) return ans代码逐行解读set(nums)一次遍历完成去重同时将原始数组的重复元素剔除避免后续重复统计对应示例 2 中的两个0if num - 1 not in nums_set序列起点的判定条件是 $O(1)$ 复杂度的来源while curr_num 1 in nums_set利用哈希表 $O(1)$ 查询能力逐格向外延伸当前序列ans max(ans, curr_streak)内层循环结束后用当前序列长度刷新全局答案。3.4 正确性验证以示例 1 的nums [100,4,200,1,3,2]手动推演集合为{1, 2, 3, 4, 100, 200}遍历到10 not in set起点成立延伸2 → 3 → 4curr_streak 4ans 4遍历到21 in set跳过遍历到3、4前驱均在集合中跳过遍历到10099 not in set起点成立100 1 101不在集合curr_streak 1ans保持 4遍历到200同理curr_streak 1最终返回4。✅3.5 复杂度分析时间复杂度$O(n)$。将数组存入集合进行去重$O(n)$集合成员查询x in set$O(1)$平均情况哈希表特性遍历集合时所有「非起点」元素只被检查一次前驱后即跳过所有「起点」元素引发的内层while延伸总步数不超过 $n$因为每段连续序列只会从其起点被完整遍历一次序列之间互不重叠。综上整体为 $O(n)$满足题目约束。空间复杂度$O(n)$。需要额外的哈希集合存储所有不重复元素最坏情况下数组元素全部不同集合大小等于数组长度。3.6 注意事项遍历的是nums_set集合而不是原始nums可避免重复元素导致的重复起点判断集合大小写敏感、数值范围可达 $\pm 10^9$因此不能使用计数数组/布尔数组模拟集合空间不可行这正是必须使用哈希表的原因——哈希表只存储实际出现过的元素与数值范围无关。4. 思路 2并查集Union Find视角题目标签中同时标注了「并查集」说明该题存在基于并查集的建模方式。虽然哈希解法更简洁但理解并查集版本有助于打通「连通性」思维并可复用仓库中的并查集专题文档与其基础实现源码。4.1 建模思想将每个数字看作一个节点数值上相邻的两个数差值为 1之间建立一条「连续边」。那么一个连续序列 ⇔ 一张连通分量最长连续序列的长度 ⇔ 节点数最多的那个连通分量的大小。具体步骤可设计为使用哈希表建立「数值 → 下标」的映射把可能很大的数值域压缩到 $[0, n)$ 的索引空间因为 $-10^9 \le nums[i] \le 10^9$直接以数值建数组不可行初始化并查集每个元素自成一个集合遍历每个元素x若x 1存在于映射表中则执行union(x, x1)统计每个连通分量的节点个数取最大值。4.2 与仓库并查集实现对应仓库中的并查集基础实现提供了三个核心接口可直接套用于上述流程find(x)查找元素根节点路径压缩版self.fa[x] self.fa[self.fa[x]]为隔代压缩union(x, y)合并两个集合返回是否发生合并is_connected(x, y)判断两元素是否同属一个集合。需要额外补充的是统计连通分量大小时需要在union成功后维护size数组按大小合并的并查集变体可参考仓库中的 tree_unionFind_UnoinBySize.py每合并一次就将两集合大小相加最后取最大size即可。4.3 两种思路的对比对比维度哈希表思路思路 1并查集思路思路 2时间复杂度$O(n)$去重 起点延伸$O(n \cdot \alpha(n))$接近 $O(n)$含路径压缩与按秩/按大小合并空间复杂度$O(n)$哈希集合$O(n)$fa 数组 哈希映射 size 数组代码量少约 8 行核心逻辑较多需实现并查集类思维视角顺序延伸连通分量合并面试中优先推荐哈希表解法代码短、易解释、无额外类定义负担并查集解法适合在考察「连通性建模」的场合展示或作为复习并查集原理的载体。5. 易混淆题型辨析连续 vs 递增 vs 子序列本仓库题解体系中存在多道名称相近的题目理解差异可避免面试中张冠李戴0128. 最长连续序列本题要求数值连续差值恰为 1元素可无序O(n) 哈希解法LCR 119. 最长连续序列与本题完全同构的 LCR 版本解法相同0300. 最长递增子序列要求严格递增差值至少为 1且保持原数组相对顺序属于单串线性动态规划问题时间复杂度为 $O(n \log n)$ 或 $O(n^2)$详见线性 DP 专题中的练习题目列表。一句话总结本题的「连续」只看数值邻居关系、不看原数组顺序因此集合哈希表天然适配而「子序列」类问题必须保留顺序约束需借助 DP 状态设计。6. 在《算法通关手册》中的定位与延伸学习本题被《算法通关手册》收录于多个关键位置面试 100 题列表 与面试 200 题列表标注为「并查集、数组、哈希表 / 中等」题解总列表 与题目分类列表可在哈希表分类下找到本题及其姊妹题。围绕本题的核心知识点仓库提供了成体系的配套资料哈希表原理哈希表专题系统讲解哈希函数直接定址法、除留余数法、平方取中法、基数转换法等与哈希冲突解决开放地址法、链地址法是理解本题set查询 $O(1)$ 的底层依据并查集原理与实现并查集专题 讲解快速查询基于数组与快速合并基于森林两种实现配合 tree_unionFind.py、tree_unionFind_QuickUnion.py 等源码可深入理解find/union的实现细节与路径压缩优化。总结本题的核心考点可浓缩为三点识别 O(n) 约束排序法 $O(n \log n)$、暴力枚举法 $O(n^2)$ 均不合格必须借助哈希表只从序列起点延伸通过num - 1 not in set判起点保证每个元素至多访问一次是 O(n) 成立的充分条件理解去重的必要性重复元素不影响答案却会破坏计数集合天然解决此问题。掌握哈希表解法后可进一步用并查集视角重新审视本题并借助仓库中的哈希表、并查集专题文档巩固底层原理为后续处理「连通分量」「区间合并」类问题打下基础。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐128. 最长连续序列Longest Consecutive Sequence——哈希表空间换时间的 O(n) 解法详解128. 最长连续序列Longest Consecutive Sequence——哈希表空间换时间的 O n 解法详解 本篇基于 LeetCode 题解仓库文档教程知识库LeetCode 128 最长连续序列从哈希集合到 O(n) 最优解的全解法剖析leetcode 仓库实战LeetCode 128 最长连续序列从哈希集合到 O n 最优解的全解法剖析leetcode 仓库实战 导读 本文围绕 LeetCode 128「Lon示例工程教程LeetCode 128 最长连续序列Longest Consecutive Sequence四种解法全解析从暴力到 O(n) 哈希优化LeetCode 128 最长连续序列Longest Consecutive Sequence四种解法全解析从暴力到 O n 哈希优化 导读 本文以 ar示例工程教程上一篇Hello 算法实战回溯算法框架下的二叉树路径搜索preorder_traversal_iii_template 模板代码全解析下一篇OpenRC 开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考