刷题群里有同学吐槽说LeetCode Hot 100里的「最长连续序列」是他见过的“最不讲武德”的题目之一。刚一看觉得很好做排序后从头到尾数一遍就行了然后瞄到题目要求时间复杂度必须O(n)人就愣住了。这道题属于典型的“思维题”——不考递归、不考动态规划、不考花哨的数据结构就考你能不能把“连续”这个概念和哈希集合结合起来。我最早做这道题的时候也是排序一把梭提交后看着性能排名哭笑不得。今天把完整思路、手写代码、面试追问和踩坑记录都整理出来希望让卡在这道题上的朋友少走弯路。1. 先看题目三个隐藏的坑每一个都能卡人1.1 连续不是相邻重复不能算多次题目给的是一个未排序的整数数组要求找出数字连续的最长序列的长度。很多人第一眼会把“连续”理解成“数组里相邻位置连续”这是第一个误区。比如nums [100, 4, 200, 1, 3, 2]数字连续的最长序列是[1, 2, 3, 4]长度是4。这些数字在数组里压根不是按顺序挨着的甚至4和1之间还隔着一个200但它们数值上是连续的。第二个坑是重复元素。题目说的是“序列”序列里的元素是从数组里选出来的重复数字不能算多次。举个例子[1, 2, 2, 2, 3]1和3之间有2但2出现了三次连续序列仍然是1-2-3长度是3而不是5。你如果直接排序后遍历并统计连续递增的段数遇到重复数字必须跳过否则就会多算。很多初学者在本地测试单测用例能过一提交发现结果偏大多半就是忘了去重。第三个坑写在题目末尾时间复杂度要求O(n)。这个限制直接砍掉了一大批“正常人能想到的解法”。换句话说这题考的不是你会不会写循环而是你能不能设计出线性时间复杂度的算法。从面试角度看这种限制本身就是提示——它暗示了某个数据结构能在O(1)时间内完成“判断某个数存在”的操作那就是哈希表。1.2 复杂度限制O(n)排序法为什么直接出局先看大家最容易想到的几条路线以及它们各自死在哪儿。最暴力的思路是对每个数字尝试从它开始不断加1看加完之后的数是否在数组里。这个思路简单到什么程度呢两层循环外层遍历所有数字内层从当前数字开始连续探测最坏情况下数组是1到n的连续递增每个数字都要往后探测n次再加上每次探测都要扫描数组判断存在性整体复杂度大概是O(n^3)。n稍微大一点就完全没法看。排序法是个巨大的进步。先排序再遍历一次相邻数字如果差值为1就累加计数否则重置。排序本身是O(n log n)遍历是O(n)总体O(n log n)。代码好写、思路直观而且大多数时候能通过测试。但题目白纸黑字写了O(n)排序法的复杂度就不满足要求。更麻烦的是排序法对原数组做了修改如果允许原地排序有些面试官还会追问这一点。想靠排序法混过去基本行不通。排序法的教训其实很有价值当你看到一个要求在O(n)时间内解决的问题第一反应不该是“我要找更快的排序算法”而是“我能不能不用排序就完成这个任务”。排序能做到的事哈希集合往往也能做到而且常常更快。1.3 这道题在考什么哈希表 剪枝思维我把这题归类为“哈希表应用 剪枝思维”的典型题目。它不考动态规划、不考贪心、不考双指针核心就一句话能不能用一个哈希集合让“判断连续”这件事变得高效同时通过剪枝避免重复计算。这里的“剪枝”非常关键。最朴素的想法是把所有数字放进哈希集合然后对每个数字都往后数连续的长度也就是每个数都当一次起点。这样做的复杂度是多少最坏情况下数组是[1, 2, 3, ..., n]第一个数往后数n次第二个数往后数n-1次总次数是n (n-1) ... 1O(n^2)。虽然查找变成了O(1)但重复计算仍然严重。仔细想想如果当前数字是3而2在数组里存在那么从3开始往后数的结果一定是“从2开始往后数”的结果的子集。也就是说3根本不是它所在连续序列的起点。真正需要从它开始统计的只有那些“前一个数不存在”的数字。用代码表达就是if (!numSet.contains(num - 1))才进入计数逻辑这就是剪枝。每个数字只会作为某个序列的起点被处理一次整个内层循环的总工作量立刻降到了O(n)。这个剪枝思路在各种算法题里都会出现本质就是“识别出哪些计算是冗余的然后跳过它”。面试的时候能把这点讲清楚比机械地报出代码有价值得多。2. 核心解法拆解为什么哈希集合能写到O(n)2.1 第一步把所有数字装进HashSet解法第一步是把数组中的全部数字放入一个哈希集合。这一步做了两件事一是去重重复数字只保留一份避免后面统计长度时重复计数二是把“判断某个数字是否存在”的时间复杂度降为平均O(1)。在Java里用HashSet在Python里直接用set()。这里要强调一个细节往集合里放的是数字本身而不是下标。刚才说过连续序列是数值上的连续和数组位置无关所以数组下标在这个问题里没有任何用处。你要回答的只有一个问题某个数字在不在集合里。HashSet.contains()和Python的in都是O(1)平均复杂度这一步为整个算法提供了地基。数据结构的选型可以做个简单对比方案查找复杂度去重能力适用性数组/ArrayListO(n)需手动处理数据量小但整体无法O(n)排序后数组O(log n)需跳过重复排序本身O(n log n)HashSetO(1)平均天然去重本题正解装了HashSet之后数组本来的顺序已经不重要了。你可以把它理解成把所有数字倒进一个盒子里盒子里每个数字只有两种状态有或者没有连续不连续不取决于它们在盒子里的排列顺序。2.2 第二步从每段连续序列的起点开始数核心逻辑可以拆成三个动作。第一个动作是遍历集合中的每个数字。注意是遍历集合不是遍历原数组。遍历集合的好处是天然去重[1, 2, 2, 2, 3]这个数组放进集合后只剩1, 2, 3你只需要处理这三个数。第二个动作是判断当前数字是不是某段连续序列的起点。判断条件是num - 1是否存在。如果num - 1存在说明当前数字不是所在连续序列的第一个数从它开始统计是白费功夫直接跳过。这个判断每次只花O(1)时间但能把总计算量从O(n^2)降到O(n)。第三个动作是只有当num - 1不存在时才从num开始用while循环不断检查num 1、num 2……是否存在同时累加长度。这个过程本质上是“顺着连续的值一路数下去”直到某个数字不在集合里为止。数完一段后用当前长度更新全局最长长度。举个例子集合里有{100, 4, 200, 1, 3, 2}。遍历到100时99不存在所以从100开始数101不存在长度1遍历到4时3存在跳过遍历到1时0不存在这是起点从1数到2、3、4得到长度4。这才是正确答案。2.3 复杂度为什么是O(n)均摊分析这一步是面试时最容易讲不清楚的地方也是这题真正的精髓。外层循环遍历了整个集合共n个元素每个元素会做一次O(1)的contains判断这部分是O(n)。内层while循环表面上看结构复杂但因为有了“只有起点才进入”的剪枝条件每个数字至多在内层循环中作为“后继”被访问一次。换句话说某一段连续序列[x, x1, x2, ..., y]只有x会启动while循环循环会依次访问x1, x2, ..., y这些数字在其他任何起点启动的while循环里都不会再被访问。把所有while循环访问的元素次数加起来每个元素最多贡献一次所以内层循环整体是O(n)。外层O(n)加内层O(n)总复杂度O(n)。空间复杂度是O(n)因为HashSet最坏情况下需要存n个数字。理解这个均摊分析有一个生活化的类比想象你有一抽屉袜子要找最长的一段连续编号。如果你拿每只袜子都向后翻找你会翻很多次但如果只从“没有前一号的那只袜子”开始翻每只袜子最多被你拿到手里一次总操作次数就控制住了。这里有个容易混淆的点要说清楚contains操作平均是O(1)但最坏情况下哈希冲突严重时会退化。不过在面试场景和LeetCode实际数据下哈希表的O(1)是成立的不用在复杂度分析里纠结最坏情况面试官要听的就是均摊O(n)的结论。3. 手写AC代码从Java到Python的实现细节3.1 Java版完整代码与逐行注释先说Java版本这是面试中最常用的语言之一也方便对比其他解法。完整代码先贴出来class Solution { public int longestConsecutive(int[] nums) { SetInteger numSet new HashSet(); // 第一步把所有数字放入哈希集合去重 for (int num : nums) { numSet.add(num); } int maxLen 0; // 第二步遍历集合而不是遍历原数组 for (int num : numSet) { // 剪枝如果num-1存在说明num不是连续序列起点 if (!numSet.contains(num - 1)) { int cur num; int curLen 1; // 从起点向后数连续的数字 while (numSet.contains(cur 1)) { cur 1; curLen 1; } maxLen Math.max(maxLen, curLen); } } return maxLen; } }有几个细节值得单独拎出来讲。第一外层遍历的是numSet而不是nums。如果遍历原数组重复元素会导致同一个连续序列被反复统计。虽然剪枝条件下重复的数字也会因为num - 1存在而跳过但如果数组里有大量重复值遍历集合更清爽逻辑更符合“集合里每个数字只处理一次”的语义。第二maxLen初始化为0。这覆盖了空数组的情况集合是空的外层循环一次不执行返回0。如果数组只有一个元素比如[5]5的num - 1即4不存在进入内层循环416不存在curLen为1返回1。第三while (numSet.contains(cur 1))里一定要记得在循环体内更新cur。有人图省事直接写while (numSet.contains(num 1))那会陷入死循环或永远数不出正确长度。3.2 Python版几行搞定Python的写法更加简洁关键是代码量更少、可读性更好class Solution: def longestConsecutive(self, nums: List[int]) - int: num_set set(nums) max_len 0 for num in num_set: if num - 1 not in num_set: cur num cur_len 1 while cur 1 in num_set: cur 1 cur_len 1 max_len max(max_len, cur_len) return max_len注意Python写in操作时要养成用集合的习惯。如果你用的是listnum - 1 not in nums这一步就是O(n)整体复杂度直接变成O(n^2)这题就没法AC了。set的in才是O(1)。刷题时不注意这点特别容易翻车本地小数据集看不出问题提交后大数组直接超时。还有一次性传入set(nums)和for num in num_set的写法让“去重”和“遍历集合”合二为一非常符合Python风格。不过有一点值得注意set(nums)会创建新的集合对象原数组保持不变。空间复杂度O(n)是绕不开的。3.3 实现细节中的两个“小魔鬼”第一个魔鬼是内层while循环的边界条件。假设集合里有{1, 2, 3, 4, 5}从1开始1的num - 1即0不存在进入循环cur从1逐渐变成5curLen从1到56不在集合中循环终止maxLen更新为5。整个过程正确没有数组越界问题。因为集合的contains方法是纯查询不涉及下标访问所以不存在“越界”这种说法这也是哈希集合会比数组方便的地方。第二个魔鬼是num - 1检查的方向。让我把这里说得细一点有的题解会写if (!numSet.contains(num 1))再从后往前数即处理递减序列。这种写法也能AC但理解成本和代码可读性都不如统一从起点向后数。关键是你要保持一致性检查前一个数、从当前向后数每一步逻辑要形成闭环。实际写的时候千万别混搭比如检查num - 1却数num - 1, num - 2的递减或者检查num 1却从num向后加1都会逻辑错乱。我还想补充一个很多初学者会忽略的点不要试图在统计过程中删除集合里的元素来“优化”。有些同学认为既然已经统计过2、3、4了就把它们从集合里删掉外层循环能少几个元素。这在原理上是可行的Java里用Iterator删除会有额外复杂度Python里边遍历边修改集合直接报错。当前这个解法已经足够高效没必要画蛇添足。4. 实战踩坑实录那些让代码从TLE到AC的教训4.1 常见错误速查表这题在LeetCode上的错误提交集中在超时和答案偏大两类。下面这张表我根据自己做题和解惑的经验整理过非常实用错误类型表现原因修复方案用list.contains大数组超时Java的List.contains是O(n)换成HashSetPython用list判断in提交TLEin在list里是O(n)换成set外层遍历原数组答案偶尔正确但重复数字多时浪费重复元素被重复处理改为遍历set/numSet没检查num-1答案正确但超时每个数都向后数O(n^2)加上剪枝判断while里忘记更新cur死循环或长度停在1cur没有递增在循环体里cur 1数组排序后统计并去重正确但复杂度O(n log n)不满足题目要求改用HashSet最危险的是“答案正确但超时”这种情况跑小数据集全过一交大用例全是红色TLE。我第一次做这题就是这样排序法在LeetCode上其实能通过不少测试用例但就是卡在最后一个超大数据集上这种失败最打击人。排查方法很简单把输入数组换成[1, 2, 3, ..., n]这样的最坏情况数一下内层循环总执行次数立刻能看出问题。4.2 面试官连续追问怎么答面试中做完这道题面试官大概率会追加一些问题。你得提前把答案准备好。第一个高频追问是“为什么要用HashSet而不是HashMap”。回答要点HashMap还需要关注键值对这里只需要判断存在性不需要存储额外信息所以HashSet的语义更准确。实现层面HashSet底层就是HashMap但面向的问题不同用HashSet代码更简洁。第二个追问是“空间复杂度能不能优化到O(1)”。这是一个比较有难度的追问。答案是可以尝试但需要牺牲时间或者修改原数组。比如先排序再遍历空间复杂度能到O(1)原地排序但时间复杂度变成O(n log n)。如果题目不强制O(n)时间这是一个合理权衡。如果硬要同时满足O(n)时间和O(1)空间在通用场景下没有简单解法可以跟面试官讨论基数排序、位图等思路但不要装懂承认限制并说明取舍就好。第三个追问是“重复元素怎么处理”。你只需要指出HashSet天然去重即可。面试官可能会继续问如果换成List你需要怎么改才能正确这时候要说要么排序后跳过重复值要么用marked数组标记。核心是让每个数字只参与一次统计。第四个追问更进阶“如果你的内存装不下所有数字怎么办”这是考察大数据处理的思路。可以先说外部排序配合分块处理也可以提一下布隆过滤器做近似判断但精度会有损失。在面试里遇到这种题重点不是给出完美答案而是展示你有“数据规模变了之后算法要随之调整”的敏感度。4.3 容易混淆的题最长连续序列和最长非降子序列刷题热词里经常把“最长连续序列”和“最长非降子序列”放在一起很多朋友会搞混。这里必须明确区分最长连续序列要求的是数值上的连续比如1、2、3、4数字之间严格相差1而且只关心数字是否在数组里出现过最长非降子序列是动态规划领域的经典问题要求的是“保持原数组相对顺序、可以不连续、非递减”的子序列。打个比方最长连续序列就像查一段连续的编号牌少一个号都不行最长非降子序列就像从一列队伍里挑几个人出来他们的身高依次不降低中间隔了谁无所谓。这两个问题对应的数据结构也完全不同。最长连续序列用哈希集合核心是存在性查询和剪枝最长非降子序列用动态规划或者贪心二分核心是状态转移和子序列长度累加。如果你在LeetCode上搜Hot 100发现有道题叫“最长递增子序列”别把这两题混为一谈。面试官如果故意把这两题放在一起问八成是想考察你区分“连续性”和“有序性”的能力。4.4 一道差不多的变体加上“返回具体序列”怎么办面试官在写完这道题后常会追加一个变体不仅返回最长长度还要返回这个连续序列本身。比如[100, 4, 200, 1, 3, 2]要输出[1, 2, 3, 4]。这时候思路基本不变只是在while循环里额外记录起始数字和长度或者把访问到的数字收集进一个列表。具体做法检测到num是起点后从num开始用一个临时列表依次添加current直到current1不存在。循环结束后如果当前序列长度大于历史最长长度就把临时列表拷贝出来。这里有一个需要注意的坑如果数组里存在多段相同长度的最长序列题目没有明确规定时可以默认返回第一段即可但最好在注释里说明或者在实现时选择编号最小的那段避免面试官觉得你考虑不周。5. 最后再分享一个小技巧用边界值自测你的代码题目写完之后不要急着提交先用几个边界用例自测一下。我的习惯是准备五组数据空数组[]应当返回0。单元素数组[7]应当返回1。全重复数组[2, 2, 2, 2]应当返回1。负数混合数组[-3, -2, -1, 0, 1]应当返回5。以及一段中间断开的数组[1, 3, 5, 7, 9]应当返回1。负数的情况尤其值得测因为num - 1在负数上同样适用没有特殊情况但新手容易怀疑“负数和正数能不能连起来”。[-3, -2, -1, 0, 1]这个例子就很好地说明了连续序列可以从负数开始一直延伸到正数哈希集合完全不关心正负号。我后来做这道题还发现一个心态层面的收获第一遍用排序法AC过的人多半不会觉得这题难但真正理解了HashSet剪枝之后才会发现自己之前压根没抓到题目核心。这个从“能过”到“理解为什么能过”的转变是整个Hot 100刷题过程中最有价值的部分之一。希望你也能从这道题里体会到一个简单的数据结构加上一个好的剪枝策略能带来多大的性能提升。