1. 从面试官视角先聊两句最长连续子数组这道题几乎每一次技术面算法环节都有可能碰到。我身边很多同事出去面试候选人也喜欢用它做开场题不是因为这道题有多难而是它特别能区分一个人是真写过代码还是只背过答案。这道题常见问法大概是“给定一个整数数组找出一个最长的连续递增子数组的长度。”很多人看到“连续”两个字就开始怕但其实它考的并不是什么奇技淫巧而是你对数组遍历、状态记录和复杂度分析的基本功。一个合格的解法应该能说清楚三层东西第一层是暴力怎么写第二层是怎么优化到一次遍历第三层是为什么这样优化不会漏解。这才是面试官想听的完整逻辑链。这篇文章我会把最长连续子数组的题目拆开揉碎从暴力解法一直讲到线性解法再延伸到一个非常像但其实是两种做法的变种题——最长连续序列。对了我还会把面试现场容易被追问的细节、边界条件、常见踩坑都整理出来。不管你是在准备校招、社招还是只是想把这一类数组题吃透这篇都能给你一个可以直接拿去用的大脑框架。读完之后你会发现连续子数组问题的核心就一句话如何用最少的遍历次数维护当前最优解。2. 拿到题先别急着写连续子数组到底在考什么2.1 题目描述里的“连续”二字往往是最大的提示先看一道最经典的版本给定一个未排序的整数数组找到最长连续递增子数组的长度要求子数组中的元素在原数组中连续出现且严格递增。示例[1, 3, 5, 4, 7]答案是 3对应[1, 3, 5]。注意不是 4因为1, 3, 5, 7虽然递增但 7 不在 5 的后面它们在原数组里并不是连续出现的。这就是“连续”和“子序列”最大的区别。子序列可以跳着选子数组不行它就像你从一列队伍里截取一个连续的区间中间不能断人。面试里凡是看到“连续子数组”“子串”这类词你脑子里第一反应应该是遍历时只需要关注当前这一段不用像子序列那样回头去看前面的所有状态。还有一点要提醒题目里说的是“严格递增”也就是1, 2, 2, 3这种遇到相等的 2 就算断了。这个细节在后面边界测试里很关键很多人一紧张就写成非递减。2.2 先区分清楚这是“子数组题”而不是“子序列题”面试现场我见过不少候选人一看到最长 xx 就先报 DP动态规划说“子序列用 DP子数组也用 DP”。这个说法不算错但它混淆了问题的复杂度级别。最长递增子序列LIS因为可以跳过元素光是确定当前元素能否接在前面某个元素后面就需要往前遍历历史状态复杂度通常是 O(n²)优化版本也要配合二分查找才能做到 O(n log n)。最长连续递增子数组只能取相邻连续段所以判断条件只需要看“当前元素是否比前一个元素大”这一个状态。它压根不需要 DP 的“择优”用一个变量记当前连续长度就够了。换句话说连续子数组问题因为有了“连续”这个强约束反而从一道中等偏难的 DP 题降级成了扫描题。面试时你如果能主动把这一点讲出来告诉面试官“为什么这里不需要 DP”会显得你不仅会写代码而且理解了解法背后的结构这比闷头写一堆状态转移方程要加分得多。2.3 题目场景往往藏在真实需求里我搜了一圈近期围绕“最长连续子数组”这个热词的讨论发现大家其实不只关注面试题本身还会联想到实际业务里的相似场景。比如股票数据里找连续上涨的最长天数、日志系统里找耗时持续超标的最长时间段、传感器信号里找持续上升的波形片段这些场景本质上都是同一个问题在一串序列里找满足某个单调条件的最长连续片段。所以这道题的解题思路放到真实工程里也是能直接用上的。你现在理解了为什么它这么高频它不是一道偏题怪题而是一类扫描问题的代表。3. 暴力解法先把复杂度说清楚再开始优化3.1 双层遍历的直观写法暴力解法的思路非常直白把每一个位置 i 当作子数组的起点从 i 开始往后推只要后面元素严格递增就把长度加一一旦断了就记录这一段长度然后换下一个起点。举例来说数组[1, 3, 5, 4, 7]从下标 0 开始1 33 55 4所以以 0 为起点能得到长度 3从下标 1 开始3 55 4得到长度 2从下标 2 开始5 4得到长度 1从下标 3 开始4 7得到长度 2从下标 4 开始长度 1。最终答案取最大值也就是 3。从代码角度来说你需要两层循环外层枚举起点内层从起点往后走直到不满足严格递增为止。最长情况下比如整个数组本身就是严格递增的内层循环几乎每次都要走到数组末尾总操作次数接近 n (n-1) ... 1也就是 O(n²) 的时间复杂度。空间复杂度倒是很省只用几个临时变量O(1)。3.2 暴力法的隐藏问题大量重复计算暴力解法虽然能通过小规模样例但只要数组长度达到十万量级O(n²) 的复杂度基本就跑不动了。为什么会这么慢关键在于它把已经验证过的递增关系反复重新计算了一遍。举个例子[1, 2, 3, 4, 5]明明是一个整体递增的数组。暴力解法从下标 0 开始数到 5得到长度 5然后从下标 1 开始又数一遍[2, 3, 4, 5]再从下标 2 开始数[3, 4, 5]…… 下标 1 到下标 4 这一段明明已经知道它肯定是递增的了暴力解法还是会傻傻地再走一遍。这个问题其实透露了一个非常重要的优化信号如果一段区间已经被验证是连续递增的那么这段区间内部的信息是可以复用或者直接跳过的。顺着这个思路走下去就能自然想到滑动窗口或单次遍历的解法。3.3 面试中什么时候可以先用暴力我也不是让你面试的时候一上来就写最优解。如果你面对的是变形题、特别复杂的扩展题或者短时间内没有清晰思路先讲一个暴力解法是完全可接受的。你可以这样说“我先给出一个 O(n²) 的基线解法保证正确性然后再讨论如何通过一次遍历把它优化到 O(n)。”这样做有几个好处第一确保自己和面试官对题目的理解一致第二展示你具备从简单方案逐步递进到优化方案的能力第三万一后面没有想出更优解你的基线分也能到手。但注意如果题目本身就是最经典的那道最长连续递增子数组只写暴力不写优化面试评价基本会停留在“能写代码但算法思维一般”这个档位。4. 一次遍历的滑动窗口解法最优解的核心思路4.1 从“重复验证”到“顺路记录”回到刚才那个例子[1, 3, 5, 4, 7]。你发现没有我们其实只需要从左到右走一遍就能知道所有连续递增段的信息走到 3 的时候知道当前段长度是 2走到 5 的时候知道当前段长度是 3走到 4 的时候递增断了所以以[1, 3, 5]结尾的这段结束了当前段重置为 1走到 7 的时候当前段长度变成 2。整个过程只需要两个变量一个记录“当前连续递增段有多长”另一个记录“历史最长有多长”。遍历结束后两者取最大值即可。这其实就是一个特别朴素的滑动窗口思想窗口边界就是当前连续递增段的两端当递增条件满足时右边界不断扩展同时更新窗口长度一旦条件被破坏左边界直接跳到新位置窗口重新开始。4.2 为什么这个解法不会漏解我知道你可能会问每到一个元素只是比较它和前一个元素的大小真的能覆盖所有的连续段吗答案是能。因为题目要求的是“连续且递增”而递增性质本身是局部的一个连续子数组整体递增等价于它内部任意相邻两个元素都满足后一个大于前一个。一旦相邻元素不满足这个条件任何跨过这个断点的子数组都不可能整体递增。所以遍历时只需要在断点处切一刀把当前段长度重置然后继续往后数就覆盖了所有可能成为答案的连续段。这有点像你统计一段路上连续没有红绿灯的路口数。你不需要从每个路口重新出发数一遍只需要记住当前已经连续通过了多少个路口遇到红绿灯就清零然后继续往下数最终取一个最大值就行。4.3 核心解法的流程拆解在实际写代码时整个流程可以拆成下面几步判空。如果数组长度为 0直接返回 0。这个细节千万别丢尤其是面试手写代码时判空能体现你的工程素养。初始化两个变量currentLen 1maxLen 1。为什么初始值是 1 而不是 0因为只要数组不为空单独一个元素本身就构成一个长度为 1 的连续递增子数组。从下标 1 开始遍历数组下标 0 已经作为起点被算进去了。比较nums[i]和nums[i-1]如果前者大于后者说明当前段还在递增currentLen加一否则说明递增断了currentLen重置为 1。每次更新完currentLen后按需更新maxLen取两者较大值。遍历结束后返回maxLen。时间复杂度是 O(n)因为只遍历了一次空间复杂度是 O(1)只用了常数个变量。这段逻辑如果你之前没有想透现在可以拿几个例子手推一遍。比如[2, 2, 2, 2]每走一步都遇到相等的元素不满足严格递增currentLen一直重置为 1最终答案就是 1。再比如[1, 2, 3, 2, 1]走到下标 3 时递增断了currentLen变回 1但maxLen已经记住了 3所以答案还是 3。4.4 复杂度分析的几个“对手戏”问题面试官特别爱在这个题后面追加一个问题“你这个解法的时间复杂度是多少为什么不是 O(n²)”你如果只回答 O(n)他大概率会继续追问“你能保证每个元素最多被访问几次”答案是每个元素最多被访问一次。因为我们只维护一个向前的指针从左往右扫不存在回溯。这个和滑动窗口类的双指针问题不一样——双指针有时会一个元素被左右两个指针各访问一次所以时间复杂度是 O(2n)本质还是 O(n)。而这道题的连续递增子数组解法更简单连左指针回退都不需要因为递增段一旦断了旧段不可能再被接上直接重置即可。5. 一个特别容易混淆的亲戚最长连续序列5.1 看题只差几个字做法差了一个维度面试中还有一道高频题叫“最长连续序列”题目长这样给定一个未排序的整数数组找出数字连续的最长序列的长度要求时间复杂度 O(n)。示例[100, 4, 200, 1, 3, 2]答案应该是 4因为1, 2, 3, 4是连续的。注意这里的 1、2、3、4 在原数组里并不是连续存放的它们在数组中的位置是散的你只是把这些数字找出来然后按数值拼成一段连续序列。这就和“最长连续子数组”有本质区别了子数组要求位置相邻连续序列只要求数值相邻。所以前者用一次遍历维护局部关系就行后者需要想办法把“数值上连续但位置上分散”的元素找出来拼在一起这就要用到哈希表了。5.2 哈希表解法从每个连续段的起点开始数这类题我面试时问过很多人最常见的错误就是把数组排序再数一遍。但题目明确要求 O(n)排序至少是 O(n log n)直接不符合要求。正确做法是用哈希表也就是集合来记录数组中出现的所有数字然后只从连续段的起点开始往后数避免重复计数。具体逻辑可以这样理解先把数组所有元素放进一个哈希集合里作用是 O(1) 时间判断某个数是否存在。遍历哈希集合中的每个数字 x。如果 x-1 也存在于集合中说明 x 不是某个连续段的起点跳过它不用从它开始数。如果 x-1 不存在说明 x 是一个连续段的起点。从 x 开始不断检查 x1、x2…… 是否在集合里一直数到断掉为止记录这一段的长度。更新全局最长长度。为什么只从起点开始数因为这个题最怕的就是重复计算。比如你从 2 开始能数出 2、3、4然后你又从 3 开始再数一遍 3、4这就浪费了。为了不浪费我们只从 x-1 不存在的数字开始数。这样每一段只会被数一次所有段加起来的计数次数最多是数组中元素的总个数 n整体时间复杂度就是 O(n)。5.3 为什么面试官总把这两道题放一起问我自己在面试时会这样安排先问最长连续递增子数组候选人写出滑动窗口后我再把题目改一下变成不要求位置相邻、只要求数值连续。此时刚才的解法就不管用了得换成哈希表思路。这个衔接其实是有心为之的。两道题都带“连续”二字但一个考的是“数组连续”一个考的是“数值连续”。能把这两者彻底区分开的人才是真正理解了连续类型的分类逻辑。如果你在准备面试建议你把这两道题放在一起刷刷的时候主动对比什么时候用单指针扫描什么时候用哈希集合什么时候用双指针滑动窗口。这样面试时才会形成条件反射。6. 聊聊代码以及怎么写才不容易被挑刺6.1 面向面试的代码风格要点很多人代码逻辑没问题但面试评分上不去问题常常出在代码风格上。最长连续子数组这道题虽然短但代码风格最能体现经验。先看一个细节遍历从哪个下标开始标准解法是从 1 开始因为 0 已经作为第一个元素被初始化进长度里了。但如果你把currentLen初始化为 0从 0 开始遍历也可以只是每轮都需要多写判断。两种写法对比下来前一种更自然也更方便讲清楚思路。还有一个细节是变量命名。别用a、b、cnt这种含混的命名。我建议用currentLen和maxLen或者currentStreak和longestStreak别人一眼就能看出哪个是当前长度、哪个是历史最长。6.2 手写代码时容易出的三个低级错误第一个低级错误是忘记判空。如果传入一个空数组很多解法直接访问nums[0]就崩了。虽然力扣上判空可能不算致命但面试手写代码时这属于一眼就能看到的工程素养问题很减分。第二个低级错误是混淆“递增”和“非递减”的判断条件。题目要求严格递增判断就得用写成就等于允许相等元素出现在同一个子数组里答案会偏大。第三个低级错误是在重置长度时写成 0。比如你遇到递增断了直接把currentLen 1吗对的因为当前元素自己就是一个新的长度为 1 的连续子数组。如果你重置成 0那么下一个元素进入时长度就会少算 1最终答案偏小。这个细节我见过太多人踩过坑包括当年我自己也犯过。6.3 测试用例怎么设计才能显得你专业面试时写完代码如果能主动说“我来测试几个用例”会很加分。但别只测题目给的那个例子要有足够的覆盖面。我常用的测试集是这样的普通场景[1, 3, 5, 4, 7]期望 3全部递增[1, 2, 3, 4, 5]期望 5全部递减[5, 4, 3, 2, 1]期望 1全部相等[2, 2, 2, 2]期望 1严格递增相等就算断连续段出现在中间[3, 2, 1, 2, 3, 4, 1]期望 4空数组[]期望 0只有一个元素[9]期望 1。这组用例覆盖了正常逻辑、边界条件和特殊值拿出来跑一遍能说明你考虑问题比较全面。7. 面试现场还原从读题到 AC 的完整节奏7.1 读题阶段要说的话拿到题目后不要急着写代码。先做两件事复述题目确认约束。你可以说“我理解这道题要找的是严格递增且位置连续的数组片段请问数组长度大概是什么量级有没有可能为空数值范围有没有限制”这些问题不是废话。数组长度决定了你能不能接受 O(n²)数值范围决定了你是不是需要考虑溢出。面试官听到你主动确认这些一般都会觉得你是有经验的而不只是刷题机器。7.2 思路阶段要展示的推理路径接下来讲思路。我建议按这个顺序讲“这个题最简单的做法是暴力枚举所有子数组O(n²)。但仔细想连续递增子数组只跟相邻元素的相对大小有关而且递增关系一旦断了任何跨过这个断点的子数组都不可能再递增所以我们只需要一遍扫描维护两个变量当前连续长度和历史最长长度。每一步比较当前元素和前一个元素如果递增就加一否则重置。这样时间复杂度 O(n)空间 O(1)。”这段话大概 30 秒能讲完但它把暴力解、优化动机、核心判断、复杂度全部覆盖到了。面试官要么直接说“可以写吧”要么会追问几个细节比如“为什么断点之后可以直接重置”这正好让你展开讲。7.3 写代码阶段要注意的节奏写代码的时候我习惯一边写一边说不要在纸上闷声写完一大段再给面试官看。比如写到if (nums[i] nums[i-1])时说一句“这里是判断是否继续满足严格递增”写到currentLen 1时说一句“这里把当前元素作为新子数组的起点”。这样面试官能跟上你的思路即使最后有小瑕疵他也知道你是想清楚了的。写完后把自己的测试用例逐一过一遍边过边说“当前长度变成了多少、最长长度是多少”。这一步特别能加分因为它证明你的代码不是凭感觉写的而是可以推理验证的。8. 这类题的高频变种一次帮你整理清楚8.1 变种一最长连续非递减子数组有些题目会把“严格递增”改成“非递减”也就是允许相等元素连续出现在子数组中。考的是你对条件的敏感度。解法框架完全不变只需要把比较符号从改成。但有一个细节要注意初始化的长度逻辑还是一样的单个元素长度为 1。如果你刷题时把两道题对照着做会发现其实只是符号一改其他都一样。8.2 变种二允许最多修改一个元素使连续子数组最长这是一种很常见的进阶题。比如给你一个数组你最多可以把其中一个元素的值改成任意值目标是使某个连续段最长。这种题就不能只用一个变量了通常需要记录“当前没使用修改机会的最长段”和“已使用修改机会的最长段”在遍历时根据情况合并或重置。这类题的核心思路还是在断点处做文章正常递增断了以后原本要重置但因为你手里有一次“修改”机会所以可以把断点附近的情况打平本质上是滑动窗口加状态标记。能用这个思路答出来的人说明真的理解了扫描类连续问题的本质。8.3 变种三二维化或者环状数组二维场景比如说矩阵里找最长连续递增路径这就要结合 DFS 记忆化搜索了难度会跳一个台阶。环状数组则是把数组首尾相连此时需要考虑跨越连接处的连续段常见做法是把数组复制一份延长或者用两倍长度的循环取模来模拟。面试考到环状数组的概率相对低但一旦考到它考察的还是你对“断点”的理解——环的断点被你放在了哪个位置决定了你的解法是否完备。8.4 变种四最长重复子数组这是另一个容易被名字搞混的题通常是两个数组要求找出两个数组中最长的公共子数组。注意这里的“子数组”同样要求连续。做法也不再是简单的单指针扫描而是需要动态规划或滑动哈希。这道题通常是中等偏上的难度和今天聊的这道题完全不是一个量级但如果你能理解“子数组必须连续”这个前提就更容易想到用二维 DP 去记录以两个数组中某位置结尾的公共连续长度。9. 我在实际刷题和面试中的几条经验最后说点刷题之外的体会。第一连续子数组这类题最重要的不是记住某一道题的解法而是养成一种条件反射看到“连续子数组”这四个字先想它的对立面“子序列”为什么难再想“连续”能不能帮我们省掉什么计算。如果你每一次都能把这种对比想清楚那你刷一道题等于刷了三道题。第二做题时不要一上来就打开编辑器敲代码。先在纸上画一个数组手动走一遍例子感受一下断点在哪、重置发生在哪、最长答案是在哪一步被记录下来的。我在最开始刷这道题的时候也是画了好多数组图才真正理解为什么能从 O(n²) 降到 O(n)。直接背模板过两周必忘自己推一遍才能变成长期记忆。第三如果你准备的是大厂面试除了把解法写出来一定要练习用口头语言把思路讲清楚。我见过有的候选人代码写得很干净但是让他讲思路就只会复述代码这其实是一个很大的短板。面试官需要确认你不是背题而是真的理解了解法背后的取舍。你如果能像我上面写的那样从暴力到优化、从时间复杂度到边界条件、从本题到变种把整个逻辑链讲完整你的算法面试通过率会明显上一个大台阶。最长连续子数组这道题说难不难说简单也藏着很多值得拆解的细节。希望这篇整理能帮你把它吃透下次面试再遇到的时候你不仅能写出最优解还能讲出让人信服的理由。