力扣第88题“合并两个有序数组”是我在刷力扣热题100时最先吃透的几道题之一。题目很短短到一眼就能读懂约束却不少藏着“原地操作”这道坎。很多初学者第一次提交就靠两个数组拼起来排序混过去了但面试官只要追问一句“能不能不用额外空间”立刻哑火。这题真正在训练的是你有没有“从结果反推过程”的意识——先想清楚最终数据要落在哪里再去设计循环的方向和指针的移动。这篇博文我打算从最暴力的解法一路讲到最优解把每一步取舍的“为什么”都摊开来讲再附上我实际提交时踩过的坑、改过的版本以及面试常见的追问方向。无论你是刚开始刷题还是准备面试前过一遍基础这题都值得花半小时吃透。它还是归并排序、合并K个链表、有序矩阵搜索等一堆题型的“零件级”基础值得反复练。1. 题目到底在考什么先拆需求再动手1.1 题目描述与核心约束先过一遍题面给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的有效元素数目。请合并nums2到nums1中使合并后的数组同样按非递减顺序排列。这里有个关键设定nums1的长度是m n其中前m个元素是真正要参与合并的数据后n个位置全用0占位。换句话说题目已经提前给你腾好了空间不允许你再开一个新数组必须原地操作把最终结果写进nums1。举个例子nums1nums2mn输出[1,2,3,0,0,0][2,5,6]33[1,2,2,3,5,6][1][]10[1][0][1]01[1]第二个和第三个例子是我特别建议你亲手跑一遍的边界场景很多人就是在m 0或n 0时翻了车。m 0意味着nums1里全是占位 0实际就是把nums2整个拷过来n 0则是什么都不用做直接返回。1.2 为什么这题值得反复刷这题在力扣上的地位比较特殊它是“合并”类题型的敲门砖也是面试里出现频率很高的基础题。我见过不少候选人能快速写出sorted(nums1[:m] nums2)这种一行流但问复杂度、问能否原地、问为什么从后往前写就开始含糊。这道题的价值不在于“会做”而在于你对“指针移动”和“覆盖顺序”有没有真正的肌肉记忆。从算法题的角度看它考察三个核心能力一是对循环不变量的理解——每个时刻当前填充位置以及两个指针各自指向“还没处理的最大/最小元素”二是对空间复杂度的敏感度——面试官很在意你能不能省掉那O(m)的辅助数组三是边界条件的严谨性——索引从 0 开始什么时候用什么时候用差一个符号结果就可能错得离谱。另外这道题是归并排序的“merge 步骤”的简化版也是合并K个有序链表、寻找两个正序数组的中位数、合并区间等题目的基本功。把这道题的指针逻辑彻底想通后面遇到再复杂的合并类问题思路骨架都是同一套。2. 从暴力到最优的三层解法2.1 解法一合并后排序五分钟兜底如果你只是想把题过了最简单的方式是先把nums1中有效的m个元素和nums2拼起来排序后再写回nums1。Python 写法很直白def merge(nums1, m, nums2, n): nums1[:] sorted(nums1[:m] nums2)这里我用nums1[:] ...而不是nums1 ...是为了原地修改nums1这个列表对象本身不然外层调用方的引用不会感知到变化。nums1[:m] nums2会新建一个长度为m n的临时数组sorted再产生一份排序后的副本内存开销是O(m n)时间开销是O((m n) log(m n))。这种解法适合在笔试里快速拿分适合在本地验证逻辑但不适合作为面试的最终答案。三个字不优雅。面试官看到这版多半会追问“你能不能在O(m n)时间内完成并且用O(1)额外空间”所以它只能当兜底不能当终点。2.2 解法二双指针正向合并空间换时间既然两个数组都是有序的就能用双指针逐个比较、逐个写入。最直觉的思路是从小往大合并用两个指针i和j分别指向nums1的有效部分开头和nums2开头每次把较小的那个放入结果位置。但问题来了——结果要写进nums1如果直接从nums1[0]开始覆盖还没处理的nums1原始元素比如 2、3就会被提前盖掉。怎么解决只能先把nums1的有效部分复制到另一个数组里然后再归并。def merge(nums1, m, nums2, n): nums1_copy nums1[:m] i j 0 idx 0 while i m and j n: if nums1_copy[i] nums2[j]: nums1[idx] nums1_copy[i] i 1 else: nums1[idx] nums2[j] j 1 idx 1 while i m: nums1[idx] nums1_copy[i] i 1 idx 1 while j n: nums1[idx] nums2[j] j 1 idx 1这个解法思路自然时间O(m n)但额外空间是O(m)。它最大的贡献是让你理解“正向合并必然要保存未覆盖的数据”这个矛盾从而引出最优解的核心思路——既然正向会覆盖那能不能反过来从后往前写2.3 解法三逆向双指针原地归并的正确姿势答案是能。nums1的后n个位置全是 0是题面给我们预留的“空地”。如果我们从nums1的最后一个有效坑位索引m n - 1开始由大到小填充那么每次写入的位置都处于数组末尾的空区永远不会覆盖还没处理完的数据。这里有个绝佳的类比就像停车场倒车入库你从最里面的车位开始倒后面的空位只会越空越多不会把已经停好的车撞了。正向入库才会撞车。具体做法设置三个指针p1 m - 1指向nums1有效部分的最后一个元素p2 n - 1指向nums2的最后一个元素p m n - 1指向最终数组的写入位置。每次比较nums1[p1]和nums2[p2]把较大的放到nums1[p]然后对应指针前移写入指针也前移。def merge(nums1, m, nums2, n): p1, p2, p m - 1, n - 1, m n - 1 while p1 0 and p2 0: if nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1 while p2 0: nums1[p] nums2[p2] p2 - 1 p - 1这个解法的精妙之处在于nums1前半部分的元素即使没被移动到新位置也因为“本来就在最终位置附近”而不需要额外挪动而nums2剩下的元素只需要从尾部继续往空位填写即可。时间复杂度O(m n)空间复杂度O(1)是这道题的标准最优解。3. 核心实现细节与参数选择3.1 三语言参考实现我平时习惯用 Python 刷题但面试时可能用 Java 或 C所以我把三个常用版本都贴出来方便你对照。Python 版def merge(nums1: list[int], m: int, nums2: list[int], n: int) - None: p1, p2, p m - 1, n - 1, m n - 1 while p1 0 and p2 0: if nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1 while p2 0: nums1[p] nums2[p2] p2 - 1 p - 1Java 版class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 m - 1; int p2 n - 1; int p m n - 1; while (p1 0 p2 0) { if (nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } while (p2 0) { nums1[p--] nums2[p2--]; } } }C 版class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { int p1 m - 1; int p2 n - 1; int p m n - 1; while (p1 0 p2 0) { if (nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } while (p2 0) { nums1[p--] nums2[p2--]; } } };三套代码逻辑完全一致变量命名也统一。我的建议是不要死记代码而是把“三指针模型”在纸上画一遍p1走nums1的有效尾巴p2走nums2的尾巴p走结果的位置三个方向都是从右往左。画完这张图代码自然就能写出来。3.2 为什么循环条件是 p1 0 而不是 p1 0这是个看着不起眼、写错却是致命的细节。p1初始是m - 1当m 0时p1 -1本来就该跳过第一个循环当m 1时p1要能指向索引 0 的元素。如果写成p1 0那么当p1等于 0 时循环直接退出nums1[0]这个元素就永远失去了被比较和移动的机会。举个例子nums1 [1, 0]nums2 [2]m 1n 1。第一轮循环中p1 0p2 0比较 1 和 2写入 2p2变-1循环结束。到这里nums1[0]还保存着 1恰好不需要移动所以结果凑巧是对的。但如果换成nums1 [2, 0]nums2 [1]第一轮比较 2 1写入 2p1变-1再进入while p2 0把 1 写进nums1[0]结果也正确。你发现没有nums1中剩余的较小元素其实不需要显式移动它们天然就排在结果数组的前面。这就是为什么最后只处理nums2剩余元素、不处理nums1剩余元素的原因——不是漏了是没必要。但这不代表条件可以随便写。循环内可能发生p1减到 0 后仍需继续比较的情况如果条件写成p1 0会在某轮循环p1刚变为 0 时直接终止虽然有些例子下结果碰巧不错但一旦nums2中有元素需要插入到nums1[0]之前就会出错。所以统一记两个指针都要能合法访问到索引 0条件就是 0。3.3 循环结束后为什么只需要处理 p2 剩余很多初学者看到第二个while p2 0就觉得对称地应该再写一个while p1 0。真不用。主循环结束只有两种可能p1 0或p2 0。如果p2 0说明nums2的元素已经全部放进结果了此时nums1剩余未处理的元素如果有本身就在数组前部且因为它们都小于等于已经被移动走的那些元素所以位置天然正确什么都不用做。如果p1 0说明nums1的有效元素全部被移到了结果末尾附近而nums2可能还剩若干个较小元素。这些元素需要被搬到nums1的前部也就是第二个循环做的事。写成while p2 0: nums1[p] nums2[p2] p2 - 1 p - 1另一种常见写法是num2_copy nums2[:p21]再整体切片但没必要指针循环最直观。如果是在 Java 里也可以用System.arraycopy(nums2, 0, nums1, 0, p2 1)俗称“最后一块拼图”。顺带一提很多题解在比较时写if (nums1[p1] nums2[p2])把相等情况归到else也就是优先取nums2的元素。这样不影响最终排序正确性而且对稳定性比较友好——相等元素中来自nums1的会留在相对靠前的位置。面试时如果被问到“相等时怎么处理”你可以这样回答归并排序里稳定性取决于相等元素的先后关系这里因为nums1的相等元素已经位于最终区域之前取nums2不会破坏相对顺序。4. 刷题中的常见坑与排查实录4.1 常见错误清单我把实际提交和帮人看代码过程中遇到的高频 bug 整理成了表格每一条都是真实踩过的建议直接收藏当 checklist。错误类型错误写法后果正确做法初始指针算错p m n或p n数组越界或漏写位置p m n - 1循环边界错while p1 0漏掉索引 0 的元素while p1 0忘记处理nums2剩余主循环后不写第二个 while小元素没拷贝完循环while p2 0直接在nums1上正向合并nums1[i]与nums2[j]比大小并从头写覆盖未处理的有效元素必须从后往前或先拷贝m 0时硬取nums1[m-1]p1 m - 1后直接用得到-1索引靠while p1 0跳过比较符号写反if nums1[p1] nums2[p2]时放入nums1[p1]把小的放到后面从后往前时应该把大的放后面只改nums1局部变量Python 写nums1 sorted(...)外层的nums1没变化用nums1[:] ...其中“比较符号写反”最容易在从后往前写时犯迷糊。记住一条口诀从后往前填的结果是大数在右、小数在左所以每次要取更大的那个元素放到当前位置而不是更小的。正向合并才取小的逆向合并取大的方向一变脑子里的逻辑也要跟着翻转。4.2 一次真实的排错经历我第一次在力扣上提交这题时用的是一版自以为完美的逆向双指针结果在样例nums1 [2, 0], nums2 [1]上直接翻车。当时的代码长这样def merge(nums1, m, nums2, n): p1 m p2 n p m n - 1 while p1 0 and p2 0: if nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1问题出在p1 m而不是m - 1。一开始想当然觉得“从有效元素的下一个位置开始”结果第一轮就取到了占位的 0把 0 当作有效元素参与比较最后结果变成了[1, 2]不假但那是歪打正着。换一组数据nums1 [3, 0, 0]nums2 [1, 2]就输出成了[2, 3, 1]彻底乱套。排查时我在本地把每个指针的轨迹打了出来才发现p1一开始指向的就不是有效数据。从那以后我养成了一个习惯凡是这种“有效长度和数组物理长度不一致”的题先写清楚有效区间的边界是什么。这道题里有效区间的左闭右开是[0, m)对应最后一个元素索引是m - 1所以指针初始值必然是m - 1没有第二种可能。4.3 代码风格与可读性建议力扣上很多高分题解喜欢把代码压缩到极致比如while (p2 0) nums1[p--] nums2[p2--];我很理解这种风格但我不建议你在面试时这样写。面试考的是沟通能力代码是辅助表达的工具。我比较推荐的做法是用有意义的变量名p1、p2、p配合注释说明循环不变量比如在每个循环前写一句“当前p指向下一个填充位置p1、p2分别指向两组剩余元素中的最大者”。评论区里很多人争论“到底用还是”其实都是奇技淫巧。真正该关注的是代码能否在一个逻辑下覆盖所有边界——m 0、n 0、m n 1、元素全部相等、元素交替大小。我建议你在本地至少把这几组用例跑一遍做到心中有数。5. 从一道题看一类题归并思想与进阶变体5.1 面试官最爱的几个追问我帮朋友模拟面试时常拿这题做引子后面跟一串追问每个都能从这道题长出一层第一个追问是“为什么不能从前往后”答案在于nums1的前m个位置已经存了有效数据正向覆盖会破坏还没比较的元素所以要复制副本或从后往前。追问到这里你已经把空间复杂度的权衡讲清楚了。第二个追问是“如果nums1的空间不够怎么办”常规做法是nums1扩到m n再原地合并如果扩不了就新开数组这就是正向双指针那种解法。这时候面试官其实在考察你有没有“看条件给方案”的意识而不是背一个模板。第三个追问是“如果两个数组都是从大到小排呢”思路完全对称从前往后写小值即可。很多同学只会背从后往前一换方向就懵说明没理解本质只是背了标志性代码。这个追问非常值得自己推演一遍。第四个追问是“如果有三个数组呢”那就先合并前两个再与第三个合并如果是 K 个用优先队列就是合并K个排序链表那道经典题。你会发现88 题的双指针是那个复杂解法的“最小单元”。5.2 相关题目的串联与内功相通顺着这道题往外走最先碰到的是力扣第 21 题“合并两个有序链表”。链表版本的合并同样可以用双指针只是节点指针的移动替代了数组索引的增减。区别在于链表不需要担心覆盖问题没有“原地数组”这个概念但代码结构和这里的正向合并几乎一模一样。再往外走是力扣第 4 题“寻找两个正序数组的中位数”。它要求O(log(m n))的时间所以不能完整合并只能用二分思想二分的时候依然要处理“两个有序数组如何交错推进”的问题底层还是有序归并的变体。如果你往后学归并排序理解起来也会更顺。归并排序的merge阶段就是反复调用这种双指针合并区别只是它合并的两个片段来自同一个数组。很多人在学归并排序时觉得源码晦涩其实就是因为没先吃透 88 题这种最朴素的场景。我建议按这条路线去串联刷题88 题数组归并→ 21 题链表归并→ 88 题的变体逆序归并→ 合并K个有序链表 → 归并排序手写。每一步都在复用同一种“双指针推进 比较大小 处理剩余”的套路练到后面你看到任何合并类题目生理反应就是画两根指针。5.3 刷题策略这类基础题怎么练才有手感我见过不少人刷题追求数量一天十道过完就忘。这道题属于“高频基础题”我建议你至少做三遍而且每一遍用不同的方式验证。第一遍看着题解写一遍理解思路就好目标是把代码跑通。第二遍隔 24 小时后不看任何资料手写完整解法包括边界判断和循环后处理写不出来就再看一遍。第三遍把代码删掉用“口头讲解”的方式把解法讲给一个假设的听众听讲清楚三个指针分别是干嘛的、为什么要从后往前、最后为什么只处理nums2。我在准备面试时还会额外做一步把这题的时间和空间复杂度用语言组织一遍。很多候选人能写代码但说不清O(m n)和O(1)为什么成立这其实是个很大的减分项。只要你能说清楚“每个元素最多被比较一次、最多被移动一次”面试官基本就会点头放你过。顺带一提力扣热题 100 的很多题目都是以这种“小而不简单”的题打底的。与其把 100 题刷三遍不求甚解不如挑其中 10 道基础题每道都能从暴力到最优、从原理到边界讲明白。真正面试时这种理解深度比刷题数量管用得多。我个人在实际操作中的体会是这种基础题最大的敌人不是思路不会而是写代码时对索引的“顺手自信”。指针初始化为m - 1还是m循环条件是 0还是 0这些差异肉眼很难察觉但跑用例时立刻现原形。我的习惯是写完代码不急着提交先在草稿纸上把第一个样例完整走一遍手感确认后再提交。这个方法让我在为无数道题省下了提交罚时。最后再分享一个小技巧如果你用的是 Python并且想让本地调试更直观可以在merge函数的循环体里加一句print(p1, p2, p, nums1)把每轮三个指针的状态打出来。看几轮之后你就会对“从后往前写为什么安全”产生真正的直觉而不是死记结论。这种把执行过程可视化的方式比反复背题解有效得多。