拿到 “LeetCode 88合并两个有序数组” 这道题的时候绝大多数人的第一反应是这有什么好写的两个有序数组合并排序算法的基础课标签上白纸黑字写着“简单”。但我在实际写代码、做面试评审的这些年里见过太多次在这道题上翻车的现场。有人三五分钟交出一版答案自信满满结果被面试官一句“你确定没有额外分配空间吗”问住也有人思路正确却在指针边界的细节上连环踩坑改完这处崩那处。这道题真正的价值不在“合并”本身而在于它用最少的代码量把数据原地操作、读写指针重叠、边界条件管理这些工程里最核心的问题全部压缩了进来。这篇文章就围绕这道题把这层窗户纸捅破。1. 题目拆解这道题同时考算法和工程思维1.1 题干三处细节提前把解法方向定死了先复述一下题目给定两个按升序排列的有序数组 nums1 和 nums2nums1 的长度是 mnums2 的长度是 n最终要把两个数组合并成一个有序数组并且结果要放到 nums1 里面。注意 nums1 的初始长度不是 m而是 m n也就是说它后面已经预留了 n 个空位用 0 占着。这个描述里藏着三处关键信息很多人都是一扫而过。第一处是“有序”和“升序”。有序意味着你可以用双指针线性扫描不需要排序合并的时间复杂度天生就是 O(mn)。如果你打算先把两个数组合到一起再调用排序函数思路不算错但完全没有利用题目给的前提条件面试官听到这里基本已经不打算给通过。第二处是“结果放到 nums1 里面”。这意味着必须原地修改不能返回一个新数组。这一点直接否决了大多数人脑子里冒出来的第一个解法新建一个长度为 mn 的数组然后像归并排序的 merge 函数那样把元素按顺序填进去。这个解法在算法上是完全正确的但它不符合题目的空间约束。第三处是“nums1 长度是 mn后面有 n 个空位”。这其实是出题人在暗示你空位就是给你用来做原地合并的“缓冲区域”。一个合格的做题人看到这里应该意识到答案十有八九和“从后往前填”有关。如果你没有意识到这个暗示说明你对空间利用的敏感度还不够。提示读题的时候把每一句限制条件都翻译成“不能做什么”和“必须做什么”。这道题的翻译结果就是不能用额外数组、不能用排序算法、要利用 nums1 末尾的空位。1.2 为什么“新建一个数组”这个直觉答案拿不到分我见过不少候选人一上来就写先 new 一个长度为 mn 的数组然后 p1 指向 nums1 开头p2 指向 nums2 开头谁小放谁最后把结果拷回 nums1。这段代码大概十几行逻辑清晰也很好解释。从纯算法角度看这个答案挑不出毛病时间复杂度 O(mn)空间复杂度 O(mn)。但题目要求的是就地合并你额外开了一个同规模的数组空间复杂度直接违反约束。有人可能会辩解说“反正最后还是要放到 nums1那我先开个数组再拷贝回去不也一样吗”。放在普通业务代码里这种写法非常常见甚至更安全因为你不去动原数组不容易引入覆盖问题。但这恰恰是算法题和工程代码的差异点算法题考的往往不是“能不能实现”而是“在给定资源约束下能不能实现”。空间限制在这里不是可有可无的建议而是题目的灵魂。一旦你选择新建数组就等于告诉面试官你对空间复杂度没有概念或者你读题不仔细。而且这道题如果允许使用额外空间难度会直接从“简单”跌到“送分”。它之所以被标记为简单而不是送分就是因为那 n 个空位给了你一种可能性但同时也埋了一个覆盖的坑。你必须先想明白“从前往后填会被覆盖从后往前填不会”才算真的理解这道题。2. 最常见的翻车方式正序合并覆盖数据的完整复盘2.1 一个最小复现错误写法如何在第3步毁掉原数据先看一个典型的错误写法。有人会把两个数组合并理解成“双指针从前往后扫谁小就把谁写到前面去”于是写出了类似下面的代码def merge_wrong(nums1, m, nums2, n): i, j, cur 0, 0, 0 while cur m n: if j n or (i m and nums1[i] nums2[j]): nums1[cur] nums1[i] i 1 else: nums1[cur] nums2[j] j 1 cur 1这个写法在逻辑上很像标准归并但它有一个致命问题写入位置 cur 和读取位置 i 可能会指向同一个区域。当 cur 追上了 i或者 cur 超过了 i你就可能在写入新值之后又把已经被改过的值当作“nums1[i]”读出来原始数据早就丢了。拿最经典的例子演示一下。nums1 [1,2,3,0,0,0]m 3nums2 [2,5,6]n 3。期望结果是 [1,2,2,3,5,6]。走一遍这个错误代码cur0i0j0nums1[0]1nums2[0]21 2所以 nums1[0] 写入 1。这一步没问题i 变成 1。cur1i1j0nums1[1]2nums2[0]22 2所以 nums1[1] 写入 2。i 变成 2。这里也还没问题。cur2i2j0nums1[2]3nums2[0]23 2 不成立所以走 elsenums1[2] 写入 nums2[0]也就是 2。此时 nums1 已经变成 [1,2,2,0,0,0]原来的 3 被覆盖了。j 变成 1。cur3i2j1现在 nums1[i] 即 nums1[2] 已经是 2 而不是原来的 3和 nums2[j]5 比较2 5 成立于是 nums1[3] 写入 2i 变成 3。cur4i3j1nums1[3] 也是 2和 5 比较2 5 成立nums1[4] 写入 2i 变成 4。cur5i4j1nums1[4] 是 2和 5 比较2 5 成立nums1[5] 写入 2循环结束。最终输出 [1,2,2,2,2,2]。这就是典型的“一步错步步错”。真正的 3 早在第三轮就被覆盖了后面所有判断都在拿一个错误的副本做比较结果自然全错。这个例子的重点在于覆盖不是到最后才显现的而是在某一次写入中悄悄发生。一旦原数组中的某个元素被覆盖你所有的后续判断都建立在错误的数据上而且这种错误很难通过“多跑几个用例”来发现因为它只在特定交错顺序下出现。注意正序双指针写法的本质问题是“读指针和写指针都在一个数组上且写指针可能超过读指针”。只要写指针走到读指针前面就会发生覆盖。数据规模越大交错越复杂出错概率越高。2.2 “插入式”合并与侥幸通过的两种隐蔽风险除了直接覆盖还有另一种常见的正序思路从前往后比较发现 nums2 中的元素比 nums1 当前的元素小就先把 nums1 从当前位置到末尾的所有元素整体往后挪一格腾出位置再插入。这种思路在结果上是正确的但复杂度非常高。来看复杂度推导。假设最坏情况是 nums2 中的每个元素都需要插到 nums1 的最前面比如 nums1 [3,4,5,0,0,0]nums2 [1,2,6]。第一个元素 1 要插入到位置 0需要把 [3,4,5] 整体后移移动 3 次第二个元素 2 要插入到位置 1又需要移动 4 次。整体算下来每插入一次都要做一次 O(m) 级别的移动总时间复杂度是 O(m×n)。一旦 m 和 n 达到十万级别这个代码基本就跑不动了。还有一个更隐蔽的误导情况。如果 nums2 里的所有元素都比 nums1 里的所有元素大刚才那个错误的正序双指针写法则会“侥幸通过”。比如 nums1 [1,2,3,0,0,0]nums2 [4,5,6]。因为每次比较都是 nums1 的元素更小写指针 cur 和读指针 i 始终保持同步前进写入位置永远等于读取位置自然不会覆盖到还没读过的数据最终结果正确。这种“恰好能过”的危险在于它会让当事人误以为自己写的是对的。等到面试官换一个交叉用例或者平台跑一个更复杂的测试代码立刻翻车。这种现象在工程上太常见了测试覆盖不足的时候代码看起来一切正常等到线上真实数据进来才暴露出读写重叠的隐患。这道题用一个小例子把这个道理讲得非常透彻。3. 正确解法逆向双指针如何把“覆盖风险”变成“缓冲优势”3.1 从尾部写入为什么能绕过覆盖问题既然正序写入会覆盖还没有读过的数据那最直接的解决思路就是不要从前往后写从后往前写。nums1 末尾有 n 个空位这 n 个空位就是专门留给你作为缓冲区的。你在从后往前填的时候p1 指向 nums1 有效元素的最后一个p2 指向 nums2 的最后一个p 指向 nums1 最后一个位置也就是整个合并后数组的最后。每次比较 nums1[p1] 和 nums2[p2]谁大就把谁放到 nums1[p]然后对应的指针往前移动一步。为什么这样不会覆盖关键在于一个事实nums1 有效元素的索引范围是 0 到 m-1而写入位置 p 从 mn-1 开始往前递减。在写入的整个过程中p 永远大于等于 p1。也就是说你写入的位置一定在“已经处理过的区域”的末端而 p1 指向的位置是你“还没处理到的有效元素”。因为 p 大于 p1所以写入永远不会动到 p1 以及它左边还没被读取的元素。即使某一步 p 和 p1 相遇那也说明 nums1 的有效元素已经被处理完了此时 p1 已经走到 -1后面只需要把 nums2 剩余元素原样搬过去就行。这就像两个牌堆你本来打算从顶部一张张抽出小牌放到新牌堆里但新牌堆和其中一个旧牌堆位置重叠。于是你反其道而行从牌堆底部开始抽大牌放到最末端预留的空位上。因为末端的位置原本就是空的所以你永远不会把还没抽过的牌挤掉。3.2 完整代码与逐行逻辑拆解正确写法非常简洁完整代码只有几行def merge(nums1, m, nums2, n): p1 m - 1 p2 n - 1 p m n - 1 while p2 0: if p1 0 and nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1逐行拆一下。p1 m - 1指向 nums1 中最后一个有效元素p2 n - 1指向 nums2 中最后一个元素p m n - 1指向 nums1 中最后一个位置也就是合并结果的最终位置。循环条件写成 while p2 0很多初学者不理解为什么不写成 while p 0。原因很简单p1 指向的 nums1 有效元素本来就在 nums1 数组里面如果 p2 已经走完说明 nums2 所有元素都处理完了此时 nums1 前半部分的元素天然就是有序排列不需要再做任何移动。如果继续循环只会用 nums1 自己的元素重复覆盖自己纯属浪费。反过来如果 p2 还没走完说明还有 nums2 的元素需要搬进来循环必须继续。循环体里的判断就是整个算法的核心如果 p1 还没走到头并且 nums1[p1] 大于 nums2[p2]说明当前合并序列中最大的元素应该是 nums1 这一侧的把它直接写到 p 位置p1 前移否则把 nums2[p2] 写到 p 位置p2 前移。每次处理完p 都要前移一位。注意这里判断条件是大于而不是大于等于。写成大于意味着当两个值相等时优先取 nums2 这边的元素。这个选择不影响最终结果因为相等元素在有序数组中相对顺序无所谓。但如果题目要求“稳定”也就是相同元素的相对顺序必须和原数组一致那优先取 nums2 可能会改变相对顺序。更严谨的写法是使用大于等于即 nums1[p1] nums2[p2] 时先取 nums1 的元素。实际上在从后往前的合并中要保证稳定性应该把允许相等的条件交给 nums1[p1]这样原数组 nums1 中靠前的相同元素仍然会留在更靠前的位置。不过 LeetCode 这道题不校验稳定性所以两种写法都能通过。把这点拎出来是因为面试官很可能拿“稳定”这两个字来追问。3.3 复杂度、稳定性和现场作答话术正确解法的时间复杂度是 O(mn)因为 p1 和 p2 每轮只有一个往前移动总共处理 mn 个位置线性复杂度。空间复杂度是 O(1)除了几个指针之外没有开辟任何额外数据结构完全符合题目的就地要求。在面试中写完之后不要直接说“写完了”可以主动给面试官补一段复杂度分析并且说明为什么从后往前可以避免覆盖。一个好的表述是从尾部开始比较把较大的元素放到 nums1 的尾部空位写指针 p 永远不会越过读指针 p1 尚未读取的部分因此不会破坏 nums1 中还没处理的有效元素当 p1 先走完时剩下 nums2 的元素直接搬入即可。这段话说完基本上就把这道题的得分点全部拿到了。如果你愿意多展示一些知识深度可以补充一句这种“读写指针重叠时从尾部反向操作”的思路在底层系统代码里非常常见比如内存拷贝时如果源地址和目标地址有重叠就必须考虑是从前往后还是从后往前拷贝。这句话能让面试官意识到你不仅会做题还能把它和工程经验联系起来。4. 边界条件与真实工程场景的映射4.1 四种典型边界条件的系统检查写完代码之后养成习惯把边界条件系统过一遍。这道题的边界主要围绕 m 和 n 的取值展开建议直接对照表来看边界情况条件正确行为当前代码表现nums2 为空n 0什么都不做while p2 0 不成立直接返回nums1 有效元素为空m 0把 nums2 元素整体搬到 nums1p1 -1每轮走 else 分支搬完 nums2nums2 全部小于 nums1所有 nums2 元素都比 nums1 小nums2 先填满尾部nums1 靠前正确因为最大值一定在 nums1 尾部nums1 全部小于 nums2所有 nums1 元素都比 nums2 小nums1 原样靠前nums2 放后面正确nums1 的有效元素不会被搬动其中 m 0 这个 case 值得多说一句。p1 初始值是 -1循环里判断 p1 0 为假于是每次都走 else把 nums2 的元素从尾部往前逐个放入 nums1最后 nums1 变成 nums2 的一份拷贝。这个行为完全正确而且不需要单独写一个 m 0 的特判分支。很多人在代码里额外加 if m 0 之类的判断反而容易把逻辑写乱。另一个值得注意的情况是 n 0。此时 p2 -1循环条件不成立直接结束。由于 nums1 已经是有序的原地就是结果不需要做任何事情。如果你的代码在这里多写了什么特判大概率是多余的。4.2 原地合并思想在真实工程中的使用位置看完边界再往远处想一层这道题到底在模拟什么真实场景最常见的对应场景是内存受限的系统。比如嵌入式设备、驱动固件、网络协议栈里经常需要把两段有序数据合并到同一个缓冲区但系统不允许你轻易地在堆上申请一块新内存。这时候你必须原地操作而且必须保证不覆盖还没有读取的数据。LeetCode 88 就是把这种需求抽象成了一个纯粹的算法题。另一个对应场景是数据合并类操作。比如数据库在页内部做记录合并或者日志系统把两个有序日志片段合并成一个完整日志如果目标是写回原来的存储区域几乎都会遇到同一个问题新数据写入的位置和旧数据读取的位置重叠。解决方式要么是“先算出最终位置然后从尾部写入”要么借助一块临时区域做交换。这道题本质上就是前者的一次最小化练习。还有一个更底层的联系很多编程语言的标准库在实现内存拷贝时都会区分源地址和目标地址的相对位置。当目标地址在源地址之后且两者有重叠时必须从尾部开始拷贝否则会把源数据覆盖当目标地址在源地址之前且有重叠时必须从头部开始拷贝。这段逻辑和这道题的指针方向选择如出一辙。如果你能把这个点讲出来说明你不是在背题而是真的理解了解法的来历。5. 面试官常追问的点、常见错误速查与延伸迁移5.1 四个高频追问以及怎么答这道题在面试中经常会被追问准备几个常见问题能帮你稳住局面。第一个追问通常是“为什么不用额外数组也能做”这个问题正着答就行nums1 尾部预留了 n 个空位逆向双指针把比较完的大数直接放进空位整个过程中写入位置永远不会覆盖未处理的 nums1 元素所以不需要额外空间。第二个追问是“如果允许你使用额外空间你的代码会怎么改”这其实是在考察你能不能变通。你可以立刻写出标准归并new 一个新数组双指针从头比较谁小放谁最后拷贝回 nums1。这个追问本身没什么难点但很多人会因为紧张而卡住建议提前在心里准备一下。第三个追问是“如果这两个数组是降序的怎么做”很简单把比较方向反过来即可。原来是为了避免覆盖所以从尾部写如果数组降序最大的在最前面反而应该从头部开始正向合并。这里的关键不是背“从后往前”这个结论而是理解“从哪一头写取决于哪一头是空位、哪一头不会覆盖”。第四个追问更有深度“如果数组非常大比如每个都是几 GB内存里根本放不下整个数组你怎么合并”这个问题就超出了原地合并的范畴通常的回答方向是“外部排序 多路归并”先把大文件切分成多个小块分别排序后在磁盘上按块做归并。LeetCode 88 的解法在这个场景里扮演的是最基础的两两合并算子虽然不能直接解决全部问题但理解了这道题再去学多路归并就会顺畅很多。5.2 易错点速查表与自查清单为了帮助大家快速定位问题我把这道题最常见的错误整理成了速查表易错点错误表现根本原因纠正思路正序双指针直接写输出出现重复或丢失写指针覆盖未读取数据改成从尾部逆向合并循环条件写成 while p 0多做无意义的自我覆盖没有意识到 nums1 自身元素无需处理改成 while p2 0比较时用 而不是 稳定性可能受影响相同元素来源选择不同如需稳定优先取 nums1 侧忽略 m 0 或 n 0特判冗长、逻辑混乱没充分利用循环条件用 while p2 0 统一处理插入式合并时间复杂度过高大数超时每次插入都移动后续所有元素用双指针线性合并写完之后用三件事自查第一p1 是否可能为负数负数时走哪个分支第二p2 什么时候为负数此时循环是否退出第三p 每次是否都正确递减有没有出现同一个位置被写两次的情况。这个自查过程十秒钟就能完成但能把绝大多数错误拦在提交之前。5.3 把“从后往前”的思维带到更多代码场景这道题解决之后建议你把“从后往前处理”的思维抽象出来它不是一个孤立的小技巧而是一类问题的通用解法。比如原地移除元素、原地去重如果要求不额外分配空间很多时候从后往前处理比从前往后处理更省心。再比如合并两个有序链表、合并两个区间数组、找两个有序数组的中位数这些题目或多或少女都借用了双指针思想。甚至在做归并排序的原地优化研究时你会发现各种“从尾部入手避开覆盖”的花样。做题的意义不在于记住某一道题的答案而在于把解法背后的判断模型沉淀下来当读写区域可能重叠时先想清楚哪一端是安全的从安全的那一端开始处理。LeetCode 88 之所以是“简单题”是因为代码量真的很少它之所以隐藏着常见工程陷阱是因为这道题浓缩了空间受限条件下所有数据搬移问题中最核心的矛盾。如果你能把这道题从“会写”变成“能讲清楚”那刷题的价值才真正落地。最后再分享一点个人体会。我见过太多人刷题时只看通过率题过了就赶紧刷下一道从来不回头看自己的错误解法错在哪。可实际上错误解法往往比正确解法更有教学价值。LeetCode 88 的错误解法告诉你写代码时最大的敌人往往不是逻辑想不明白而是忽略“数据会被覆盖”这个底层风险。把这个风险意识带进真实工程你能在代码上线之前省下无数个排查数据的夜晚。