力扣88题合并两个有序数组：双指针原地合并与面试必问点

如果你准备过任何一场技术面试大概率撞见过这道题——力扣88题合并两个有序数组。它顶着 Easy 难度标签却是热题100里的高频题也是我面试别人时必出的一道。说实话我面过的候选人里能把这道题从“能过样例”讲到“把原理说透”的可能不到一半。原因很简单这题表面上是归并排序的简化版考察双指针思维但题目里偏偏藏了“原地合并”的约束空间复杂度要求一下拉高。它既考思路又考基础功底还考代码习惯一道题能看出不少东西。这篇文章我会把三个主流解法先合并后排序、正向双指针、逆向双指针全部拆开重点讲清楚为什么最终版本要从后往前写、为什么不会覆盖有效数据然后把面试官最爱追问的问题和刷题时容易踩的坑一并整理出来。无论你是准备校招、社招还是单纯想巩固双指针这块知识这篇应该都能让你省下不少绕路时间。1. 先读懂题目它到底在考什么1.1 题干细节与隐藏约束先过一遍题目本身。力扣88题合并两个有序数组原题描述大致是这样的给你两个按非递减顺序排列的整数数组nums1和nums2数组里各有两个参数m和n分别代表nums1和nums2中实际有效元素的个数。nums1的数组长度是m n也就是说末尾留了n个位置给合并结果这n个位置默认用0占位。nums2的数组长度就是n。最终要把nums2合并到nums1里面然后让整个nums1保持有序。注意函数是原地修改nums1没有任何返回值。一个很典型的输入是这样nums1 [1,2,3,0,0,0], m 3 nums2 [2,5,6], n 3合并后nums1应该变成[1,2,2,3,5,6]。很多人一开始没太读懂“为什么 nums1 后面全是 0”。这里的关键在于力扣的测试环境给你分配好了m n长度的数组后面占位的0不是数据而是给合并结果预留的“空位”。题目要求你直接把结果写在这块空位里而不是另开一个新数组返回。这就带出了一个隐藏考点你是否能在不申请额外空间的前提下完成合并。1.2 为什么这道题常被拿来卡人这道题在外行看来简单得不像话两个数组都排好序了合并一下不是有手就行但真上手写情况完全不一样。我先说说我在面试中观察到的问题。第一类候选人一上来就写sort实现很快但让他优化空间复杂度一下子愣住了。第二类候选人知道要用双指针能从前往后写代码但写出来新建了一个临时数组空间复杂度还是O(mn)这本身没错但放在这道题里属于“解题没解到考点上”。第三类候选人终于写出了从后往前的标准解然而问他“为什么从后往前不会覆盖 nums1 的有效数据”他支支吾吾说不清楚。说白了这道题考的不是“会不会归并排序”而是三个层次会不会用双指针思想处理有序序列合并能不能理解“原地操作”带来的限制与机会能不能把这个过程讲明白让别人相信你是真懂而不是背了答案。这也是为什么我强烈建议刷这道题时不要只追求 ACAccept通过测试而是要在理解原理之后把代码反复写几遍再对着空气讲一遍。你如果能把这道题讲明白了双指针这块基本就通了。2. 解法一先合并再排序最快的兜底方案2.1 三行代码实现先看最朴素的思路既然最后要的是“合并后的有序数组”那我先把两个数组合到一起再整体排序不就完了吗在 Python 里这个思路甚至可以压缩成一行class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: nums1[:] sorted(nums1[:m] nums2)注意这里有个小细节我写的是nums1[:] ...而不是nums1 ...。这俩区别很大。nums1 ...是重新绑定变量函数外面原来的数组成员不会变nums1[:] ...是切片赋值直接修改原数组的内容这才满足题目要求的“原地修改”语义。如果把nums1[:] ...写成nums1 ...你在本地测试可能看不出问题因为你在函数内部打印nums1看到的确实是合并好的结果但力扣比对的是函数外部那个数组它根本不会被修改结果就是报错。这个细节我放在后面“常见坑”里还会再提这里先记一笔。2.2 复杂度与适用场景这个解法当然能通过力扣的测试毕竟题目只要求“合并后有序”并没有禁止你排序。但它的复杂度很不理想时间复杂度O((mn)log(mn))因为排序的耗时压过了合并本身。空间复杂度O(mn)因为nums1[:m] nums2先创建了一个新列表sorted()可能还会再创建一份。也就是说你完全没有利用“两个数组本来就有序”这个条件。你等于把两份已经整理好的档案扔进碎纸机再自己重新拼了一遍。能拼出来但没必要。这个解法适合什么时候用我一般建议用在笔试时间不够、只求通过的场景。比如在线测评最后五分钟你还有一道题没写这种尽是稳的兜底方案可以帮你把分拿到。但如果是面试或者你平时练习请一定继续往下看。用排序解这道题等同于告诉面试官“我知道无脑做法但没琢磨过这道题想考什么”印象分基本就没了。3. 解法二正向双指针标准的归并思路3.1 思路梳理与代码实现既然两个数组已经有序最直觉的合并思路就是双指针一个指针盯住nums1的开头一个指针盯住nums2的开头每次从两个指针指向的元素里选一个小的放进结果数组然后指针后移。这就是归并排序里“合并”那一小步的原型。但这里有个问题如果把nums1和nums2的有效元素都往nums1里直接放nums1自己开头的元素会被覆盖。比如nums1 [1,2,3,0,0,0]当我们把nums2的2写到前面时nums1原来的1,2,3还等着读取呢一覆盖就丢了。所以正向双指针的标准做法是先把nums1的有效元素复制到一个临时数组再去合并class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: tmp nums1[:m] # 把 nums1 的有效部分备份出来 p1, p2 0, 0 # 两个指针分别指向 tmp 和 nums2 的头部 p 0 # p 指向 nums1 当前要写入的位置 while p1 m and p2 n: if tmp[p1] nums2[p2]: nums1[p] tmp[p1] p1 1 else: nums1[p] nums2[p2] p2 1 p 1 # 如果 tmp 还有剩余直接续到后面 while p1 m: nums1[p] tmp[p1] p1 1 p 1 # 如果 nums2 还有剩余直接续到后面 while p2 n: nums1[p] nums2[p2] p2 1 p 1逻辑不复杂谁小谁先出像两条队伍排队进同一个闸口。最后两个while是为了处理“其中一条队已经排空另一条还剩元素”的情况。因为剩余的这些元素本来就是有序的直接搬到末尾即可。3.2 空间代价换来的清晰度值不值这个解法的时间复杂度是O(mn)只扫描了每个元素一次比排序解高效得多。但空间复杂度仍然是O(mn)准确说是O(m)因为我们额外复制了一份nums1的有效元素。从代码可读性看正向双指针其实是最好的逻辑非常直观几乎不需要动脑就能写对。这也是我给初学者的建议第一遍先写这个版本确保归并思路扎实了再去进阶。但它不是这道题想要的终极答案。题目故意给nums1预留了n个空位等于把“省空间”的机会摆在你面前。如果不去用额外搞一份tmp面试官一句“能不能不开额外空间”就能把你接下来的一段路堵死。这时候真正关键的问题就来了能不能既不新建数组又保持“谁小谁出”的顺序答案是改变方向。从后往前合并这道题的隐藏通道就打开了。4. 解法三逆向双指针原地合并的正解4.1 核心洞察尾部空位就是天然缓冲之所以正向双指针需要临时数组根本原因在于合并过程中nums1的有效区域还没被读完写入的位置就已经碰到了它。前面的元素一覆盖后面的比较就无从谈起。那我们换个角度想既然最后的位置是m n - 1而现在nums1的后n个位置全是占位符等于给我们预留了一块空白缓冲区。我们可以从数组尾部往前填充结果谁大就放在最后面依次往前倒着填。这个过程有点像搬家时从最里屋往门口搬先把靠里面的箱子移出去腾出空间再搬门口的箱子全程不需要把东西临时堆到走廊里。先看代码再来证明为什么不会覆盖class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: i, j, p m - 1, n - 1, m n - 1 # 两个数组都还有剩余元素时从尾部比较 while i 0 and j 0: if nums1[i] nums2[j]: nums1[p] nums1[i] i - 1 else: nums1[p] nums2[j] j - 1 p - 1 # 如果 nums2 还有剩余直接填充到 nums1 前面 while j 0: nums1[p] nums2[j] j - 1 p - 1你可能会问如果i 0但j 0也就是nums2已经用完、nums1还有剩余元素时怎么不处理了答案是不用处理。因为此时剩余的那些nums1元素本来就待在原位置上且位置都在当前p的前面它们已经是有序的。如果再移动反而会把已经排好的顺序打乱。这是一个容易忽略、但非常妙的收尾条件。4.2 为什么倒着写不会覆盖有效数据这是面试官最爱问的一个点也是你要主动讲明白的核心。关键在于观察三个指针的位置关系。设i m - 1它指向nums1有效区最后一个元素p m n - 1它指向整个nums1的末尾。当j 0时每进行一轮p至少会减 1而i只有当nums1[i] nums2[j]时才减 1。也就是说p的下降速度永远不慢于i的下降速度所以p始终严格大于i或者在nums2用完之后p最多等于i的前一个位置。用更严格的话说i最初是m-1p最初是mn-1两者初始差距为n。每一轮循环p必定减 1而i最多也减 1。所以直到i被读取并写入之后新的写入位置至少是i 原地步差也就是说我们永远不会把一个还没读的nums1元素给覆盖掉。因为一旦某个nums1元素被写入到靠后的位置说明这个元素已经被读取完了后面的覆盖对它来说无所谓。如果你觉得文字有点绕可以直接拿样例演示一下nums1 [1,2,3,0,0,0]nums2 [2,5,6]。初始i2指向数字3j2指向数字6p5。3 6吗不是所以把6写到nums1[5]j1p4。比较3和55大把5写到nums1[4]j0p3。比较3和23 2把3写到nums1[3]i1p2。此时nums1里原来的1,2还安安静静待在开头没有被碰过。后面的1、2继续参与比较最终结果[1,2,2,3,5,6]。关键点在于当nums1的元素被移动时它只会移动到当前位置的后面而后面这些位置要么是原来占位的 0要么是已经被处理完的更大的元素所以原数据不会丢失。4.3 完整代码与边界处理上面的展开写法已经很清楚。如果你想把代码压得更短还可以合并成下面这种写法这在很多题解里也能看到class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: i, j, p m - 1, n - 1, m n - 1 while j 0: if i 0 and nums1[i] nums2[j]: nums1[p] nums1[i] i - 1 else: nums1[p] nums2[j] j - 1 p - 1这个写法把“只剩nums2”的情况统一收进了循环条件只要j 0就继续而如果nums2已经用完循环直接结束因为nums1前半段天然有序。这种风格更高阶但不适合新手容易在面试紧张时漏条件。我更推荐前面那个展开版本逻辑分块清楚讲给面试官听也更顺畅。边界情况也要单独过一遍m 0时i -1第一个while直接跳过第二个while会把nums2全部复制到nums1结果就是nums2本身。n 0时j -1两个while都不进去nums1原样返回完全正确。两个数组都是空m 0, n 0也没问题循环直接不执行。这段代码的时间复杂度是O(mn)空间复杂度是O(1)只用了几个变量没有额外数组。这也是力扣官方题解给出的标准答案。5. 面试现场高频追问与避坑清单5.1 面试官最爱问的三个追加问题把代码写对只是开始。面试官真正想通过追问确认的是你有没有把原理想透。我整理了几个出现频率极高的问题以及我建议的回答方式。第一为什么不从前往后填这个问题直接考察你对“覆盖”的理解。回答的核心是从前往后填时nums1有效元素占据的位置就是写入目标位置写入会覆盖还没读取的元素。而从后往前填时我们是从数组尾部空闲区开始写入nums1的有效元素始终保持在自己的位置等待比较等它被比较完再搬到后面不会发生覆盖。第二如果nums2先合并完了怎么办答案是直接结束。因为nums1中未被处理的元素都是已经有序排列而且它们本就在最终位置的前段不需要再做任何操作。这一点要主动讲出来因为很多人以为必须额外写一个while i 0的循环去搬运nums1其实不需要。我见过不少人在这个点上绕进去白白多写好几行没必要的代码。第三能不能再优化成 O(1) 空间这里要分清楚逆向双指针已经是 O(1) 额外空间也就是不借助临时数组。如果面试官问的是 O(log) 或更快的时间复杂度那就需要说明在比较两个有序数组的合并问题上每个元素至少要看一次所以 O(mn) 是时间下界没法再继续压。如果面试官要求“不开额外空间但要求更快的平均时间复杂度”那么可以提一下二分法逐个插入但那样会引入大量的元素移动实际复杂度反而更差得不偿失。5.2 笔试和编辑器里的坑除了面试追问这道题在笔试环境里也有很多细节坑。第一个坑也是最常见的就是nums1[:]和nums1 的区别。前面已经说过nums1 ...只是重新绑定局部变量不会去修改函数外部那个数组。用 Python 写样例时最容易忽略这一点在顶级错误报告里看半天最后发现函数里明明打印输出是对的但提交就是不通过。出门左转搜索“力扣 88 Python 原地修改失败”你能看到无数人踩过。第二个坑是在while循环里把比较符号写反。从后往前合并时我们应该把大的元素往数组尾部放。但如果你习惯性写成了if nums1[i] nums2[j]写进去的全是小元素结果整个数组是反序的。每次写完自己手动跑一组样例先判一下顺序能省很多调试时间。第三个坑是忘了处理m 0的情况。有些人写了一个很复杂的版本各种条件嵌套但在m 0时i -1下标直接越界或者逻辑分支走到了不该走的路径。我的习惯是写完代码后用三组用例测试m0、n0、普通的非空输入。这三组用例一跑边界问题基本全暴露了。5.3 刷题平台的常见“错法”力扣的报错信息有时对新手不太友好尤其是 WAWrong Answer答案错误时。很多人在本地测试输出了正确结果一提交却报错大概率就是踩了上面提到的“重新绑定”陷阱。还有些平台比如某些白板笔试系统甚至不会给你运行样例只会把代码收走交给人工判卷。这种情况下代码风格也很重要。尽量避免把全部逻辑塞进一个巨大的while分支里清晰分行、明确变量名、提前处理好边界人工判卷时更容易拿分。你可以把i、j、p这种变量在注释里写明它们分别代表什么笔试环境里注释不扣分反而能帮你理清思路。6. 从88题延伸出去同类题怎么学、怎么刷6.1 和这道题强关联的力扣题目这道题会做了并不意味着双指针模块就学完了。我的建议是以88题为起点顺着它把一批相关题串起来刷这样知识才是网的形状。下面这些题和88题要么共享思想要么直接是它的变体力扣21题合并两个有序链表结构相同只是数组变成了链表。用链表时不需要移动元素反而更简单重点在于虚拟头节点的使用和递归/迭代两种写法。力扣23题合并K个升序链表是88题的“多路归并”版本。最常见的方案是优先队列最小堆或分治合并考察点从双指针升级到了堆和分治。力扣977题有序数组的平方给定一个非递减数组返回每个数平方后排好序。暴力法是把每个平方之后排序最优解也是双指针从两端往中间比较绝对值大小思路与88题的“从后往前”有异曲同工之妙。力扣26题删除有序数组中的重复项同样是在原数组上操作的双指针只不过一个快指针负责扫描一个慢指针负责维护结果区。力扣283题移动零快慢指针把非零元素往前搬再把后面补零。初次做时很神奇做多了就发现这类“原地整理数组”的题通用框架是差不多的。再往深一点归并排序本身也是88题的灵魂。你如果真的理解了这道题再去看归并排序中“合并两个有序子数组”那一步会觉得非常自然。换句话说88题是学习归并思想的最小切口。6.2 热题100该怎么刷这套双指针题组建议一起做很多人在刷力扣热题100时喜欢按题号顺序从1刷到100或者每天随机挑一道。我个人不建议这样。哪怕是热题100题与题之间也有明显的知识关联按题号刷会把这种关联打散效果很差。更好的做法是按专题分组比如前端刷题可以按照“数组双指针 - 链表 - 哈希表 - 滑动窗口 - 动态规划”这个顺序推进。拿双指针这一组来说我的推荐刷题顺序是先做 88合并有序数组从后往前填、26原地去重、27移除元素、283移动零这些题共享快慢指针或原地修改的思路再上 15三数之和、11盛最多水的容器、42接雨水这些题目表面上是不同题本质都是通过对撞双指针做条件判断。如果能把这几道题放在一起集中刷双指针这个模块很快就能内化成直觉后面看到新题一眼就能判断“这里面藏着双指针”。另外再分享一个我的复盘习惯每刷完一整套专题我会挑其中两三道题在空白文档里不看题解重新实现代码写完后用几组测试用例自己跑一遍然后还要能不看代码、用语言把思路讲出来。88题和21题我经常拿来做这个训练因为它们短小但完整适合检验自己是不是真懂了。最后再说点刷题之外的话这道题我刷过不下五遍每遍都有新收获。第一次是大学时照着题解敲了一遍标准解似懂非懂第二次准备面试时才发现追问“为什么倒着写不会覆盖”时自己讲不利索后来开始面试别人又从中看到了候选人不同的思维层次。回头想想88题最大的价值不是那个while j 0的模板而是它训练了一种意识当正面处理一个问题有阻碍时试着从反方向入手往往天然地规避掉许多制约条件。以后你再遇到“原地修改”“O(1) 空间”这类要求时心里可以立刻多一个备选项能不能从尾部开始能不能逆序操作这个思路在删除元素、覆盖写、原地哈希等问题里都很管用。另外还有一个小技巧写这种原地数组题时先用纸笔画一画初始状态和一轮循环后的状态比直接盯着代码想快得多。我自己刷题桌上常年放一叠草稿纸假装程序人都是痛点但真的能救命。希望这篇内容能让你的双指针之路稍微顺畅一点。