最近在整理刷题笔记把LeetCode第88题“合并两个有序数组”又从头到尾过了一遍。这道题题面短、标签简单数组、双指针难度标着Easy但实际写起来有不少容易被忽略的坑。我见过不少刚刷算法的同事一看到这道题就兴奋地写起两层for循环结果要么元素被覆盖要么数组越界要么写了一个能跑但完全没利用“有序”这个前提的糟糕实现。这篇文章不打算讲什么高深理论就围绕这道题彻底聊透题面里的隐藏信息是什么、三种由简到繁的思路怎么选、标准代码怎么一步步写出来、调试时会碰见哪些经典问题、以及面试官可能顺着这道题追问什么。无论你是刚开始刷题的新手还是准备面试想快速复习双指针这篇都能给你一些参考。1. 这道题到底在考什么读懂题面里的隐藏信息1.1 题目设定与三个容易被忽略的点先还原一下题目。给定两个有序整数数组nums1和nums2其中nums1的长度是m nnums2的长度是n。nums1的前m个元素是真正有效的元素后面n个位置用 0 占位。要求把nums2合并到nums1中使合并后的nums1依旧有序。这里藏着三个容易忽略的点。第一nums1的长度不是m而是m n。很多新手第一次写时默认nums1和nums2长度相等或者不知道从哪获取nums1的长度直接写了int[] result new int[nums1.length nums2.length]这就是没读懂题。第二题目本质要求“原地合并”。既然nums1尾部已经分配好空间出题人想让你在nums1内部把结果组织好不要额外创建一个完整的新数组。如果你养成“新建临时数组再拷回去”的习惯虽然能过却错过了这道题最核心的训练点。第三两个数组都是有序的这是一个非常强的约束。如果不利用它就跟拿着一堆排好序的扑克牌却非要重新洗牌一样既浪费已有信息也没体现出算法思维。我用一个生活化例子来帮助理解你面前有两排卡片第一排左边 m 张已经从小到大排好右边 n 个空位第二排 n 张也已经排好。现在要把第二排所有卡片计入第一排最终第一排从左到右仍然递增。那些空位就是题目给你的缓冲区如何处理这些缓冲区是解题的关键。1.2 为什么“原地合并”才是考点很多人把这道题当成“归并排序里的 merge 操作”来背这没问题但忽略了“空间限制”这个维度。如果允许开临时数组代码确实很简单跟归并排序里合并两个有序子序列几乎一样两个指针从头比谁小谁进临时数组最后拷回去。你会写归并排序就能写出这种方案。可一旦要求原地完成事情就变得有意思了。你需要思考能不能不开新数组如果需要把nums2的元素插到nums1前面原本的nums1元素是不是得往后挪挪的过程中会不会覆盖还没处理的数据怎么避免这些思考正是面试官想看到的。题目把nums1的大小特意设成m n本质就是在暗示尾部的空位是给你留好的你只需要找到一个安全的填充顺序。这个安全顺序就是“从后往前”。2. 思路演进从暴力到最优的三种方案2.1 方案一合并后排序适合当兜底策略最直接的想法是先把nums2的元素接到nums1的尾部然后对整个nums1排序。for (int i 0; i n; i) { nums1[m i] nums2[i]; } Arrays.sort(nums1);这段代码短到不能再短一眼能看懂也基本不会写错。时间复杂度是O((mn)log(mn))因为排序是主要开销。如果没有排序这个动作光拼接只需要O(n)。我自己刷题时如果笔试时间特别紧张、或者一时没想起来双指针写法会用这个方案先保住正确性。但它有一个很明显的浪费两个数组明明已经有序你却把它们混在一起重新排序完全没有利用输入数据的“有序性”。当m和n都很大时性能会肉眼可见地变差。用这个方案参加面试有一个风险面试官会追问“能不能在O(mn)时间内完成”。一旦被问到就需要切换到双指针思路。所以它适合“保底”但不太适合作为面试中的最终答案。2.2 方案二额外数组双指针思路最“教科书”这个方案就是标准的二路归并方法。public void merge(int[] nums1, int m, int[] nums2, int n) { int[] temp new int[m n]; int p1 0, p2 0, idx 0; while (p1 m p2 n) { if (nums1[p1] nums2[p2]) { temp[idx] nums1[p1]; } else { temp[idx] nums2[p2]; } } while (p1 m) { temp[idx] nums1[p1]; } while (p2 n) { temp[idx] nums2[p2]; } for (int i 0; i temp.length; i) { nums1[i] temp[i]; } }这个方案的时间复杂度是O(mn)因为每个元素最多被比较一次、被移动一次。空间复杂度是O(mn)因为额外开了一个临时数组。它的思路非常直观两个指针分别指向两个数组的开头每次比较当前元素的大小把较小的放进结果数组然后移动对应指针。某个数组先耗尽后把另一个数组剩余部分直接拷进去。这个方案已经比方案一好很多也足够应对大多数场合。但面试官如果继续问“能不能省掉临时数组”你又得往前一步。此外当数据量很大的时候额外开一块mn的内存可能不现实所以“原地合并”的价值不只是省几个字节而是代表一种更强的空间控制能力。2.3 方案三从后往前原地合并用“倒放”破解覆盖难题直接说核心思路。定义三个指针p1 m - 1指向nums1最后一个有效元素p2 n - 1指向nums2最后一个元素p m n - 1指向nums1最终的最后一个位置。然后循环比较nums1[p1]和nums2[p2]把较大的那个放到nums1[p]同时移动对应的指针和p。循环结束后如果p2还有剩余就把nums2剩余元素逐个搬到nums1前面如果p1还有剩余则不需要动因为它们本来就在正确位置。为什么从后往前能避免覆盖因为nums1的后 n 个位置本来就是空的从尾巴开始填写入位置p始终不小于p1。每填一个位置p和p1或p2一起往前移动但p1永远不会越过p。也就是说我们先把大数放到最右边而这些位置要么原本就是空位要么已经被处理过不会影响还没处理的元素。这个技巧很像倒车入库正面开进一个窄车位很容易卡住倒着进反而可以利用更大的摆动空间。数组的尾部空位就是那个“更宽松的入口”你只需要改变填充顺序就能在不额外开辟内存的情况下完成任务。3. 手把手写代码核心实现与调试实录3.1 Java版标准实现与逐行解读下面是我比较推荐的一种写法可以直接在 LeetCode 上提交。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 (p2 0) { if (p1 0 nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } } }逐行说一遍。int p1 m - 1指向nums1的最后一个有效元素。如果m 0p1 -1这也是合法的后续要用p1 0做保护。int p2 n - 1指向nums2的最后一个元素。如果n 0p2 -1那while (p2 0)一开始就不成立函数直接返回这正好符合“什么都不用做”的预期。int p m n - 1指向nums1最后一个物理位置也就是最终结果的最右边。主循环条件写成while (p2 0)而不是常见的while (p 0)。这个细节很关键。因为只要nums2的元素还没处理完就必须继续合并而nums1如果还剩元素没处理这些元素本身已经在正确的位置上不需要再移动。写成p2 0后内部再用p1 0兜底能安全处理m 0这类边界情况。循环体内部的判断逻辑是如果p1还有效并且nums1[p1]比nums2[p2]大就把nums1[p1]移到p的位置同时p1和p都减一否则把nums2[p2]移到p的位置p2和p减一。也可以把循环拆成两个阶段清晰度更高一些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--]; } }两种写法运行性能几乎一样第二种对新手更友好因为它把“比较”和“处理剩余元素”分成两个阶段不容易漏掉逻辑。3.2 Python和C实现算法逻辑在语言间是通用的只是语法上有差异。Python 版本def merge(nums1, m, nums2, n): p1, p2, p m - 1, n - 1, 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 - 1Python 的列表长度是动态的但题目保证nums1初始长度就是m n所以直接按下标修改即可。C 版本class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { int p1 m - 1, p2 n - 1, p m n - 1; while (p2 0) { if (p1 0 nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } } };C 里vectorint作为引用传入修改会直接作用到原数组。需要注意vector的长度和有效元素数量是两回事别用nums1.size()当作m。3.3 典型用例的完整单步跟踪拿题目自带的样例来手动跑一遍nums1 [1,2,3,0,0,0]m 3nums2 [2,5,6]n 3。初始状态p1 2指向 3p2 2指向 6p 5。第一轮比较 3 和 66 更大把 6 放到nums1[5]。p2变为 1p变为 4。此时数组是[1,2,3,0,0,6]。第二轮p1 2指向 3p2 1指向 5。5 更大把 5 放到nums1[4]。p2变为 0p变为 3。数组是[1,2,3,0,5,6]。第三轮p1 2指向 3p2 0指向 2。3 更大把 3 放到nums1[3]。p1变为 1p变为 2。数组是[1,2,3,3,5,6]。第四轮p1 1指向 2p2 0指向 2。相等走 else 分支把nums2[0]的 2 放到nums1[2]。p2变为 -1p变为 1。数组是[1,2,2,3,5,6]。此时p2 -1循环结束。p1 1指向nums1[1]的 2它已经待在正确位置不需要额外处理。最终结果[1,2,2,3,5,6]。再跑一个边界用例nums1 [0]m 0nums2 [1]n 1。初始p1 -1p2 0p 0。进入循环p1 0为 false走 else 分支把nums2[0] 1放到nums1[0]p2变为 -1p变为 -1。循环结束结果[1]正确。3.4 时间复杂度和空间复杂度评估时间复杂度是O(mn)。为什么因为无论是比较、移动还是最后复制剩余元素每个元素最多被处理一次没有嵌套循环也没有重复扫描。空间复杂度是O(1)。额外使用的只有三个整型指针变量不随输入规模增长。这一点是方案三最大的优势也是面试官最希望听到的结论。如果对比三个方案方案一时间O((mn)log(mn))空间O(1)Arrays.sort对基本类型数组是原地排序或O(log(mn))的递归栈开销方案二时间O(mn)空间O(mn)方案三时间O(mn)空间O(1)。方案三是真正的“双最优”这也是它成为标准答案的原因。4. 常见问题与排查技巧实录4.1 从前往后写为什么会覆盖元素这几乎是新手必踩的坑。不少人一上来就写int p1 0, p2 0, p 0; while (p1 m p2 n) { if (nums1[p1] nums2[p2]) { nums1[p] nums1[p1]; } else { nums1[p] nums2[p2]; } }用一个例子看看问题出在哪。设nums1 [1, 3, 0, 0]m 2nums2 [2, 4]n 2。初始p 0比较nums1[0] 1和nums2[0] 21 更小放进nums1[0]p1 1p 1。此时nums1还是[1, 3, 0, 0]看起来没问题。接着比较nums1[1] 3和nums2[0] 22 更小于是把 2 放进nums1[1]。这一步就把原来的 3 覆盖了nums1变成[1, 2, 0, 0]。后续 3 永远消失了。根本原因是当p超过还未处理的p1时写入位置可能落在尚未消费的有效元素上把它覆盖掉。数组不像链表没有“断开重连”的灵活性一旦覆盖就找不回来。从后往前填则完全避开这个问题因为p所在的尾部空间本来是空的。4.2 越界问题p1变成-1怎么办当m 0时p1 -1。如果在循环里仍然写nums1[p1] nums2[p2]会抛出ArrayIndexOutOfBoundsException。所以必须先判断p1 0再访问。同理当n 0时p2 -1。如果主循环条件写错比如写成while (p 0)并且内部没有对p2 0做约束也可能在nums2元素取完后仍然进入循环然后尝试访问nums2[-1]。这里可以总结成一条规则任何数组下标在访问前都必须确认自己在有效范围内。这听起来像废话但在指针类题目中越界是最频繁出现的运行时错误。4.3 为什么循环结束后只需要处理p2剩余写完后很多人会疑惑为什么nums1的剩余元素不用管可以从三个角度理解。代码层面如果nums1还有剩余说明这些元素一直在nums1的头部从后往前比较时它们要么被移动到后面要么从未被选中。从未被选中意味着它们已经躺在最终位置不需要再动。逻辑层面我们的比较原则是“谁大谁往后走”。如果某个nums1的元素比nums2里已经被填进去的所有元素都小它就不可能被选中也就不需要移动。证明层面可以用循环不变量来说明。每次循环结束时nums1[p1 ... mn-1]已经是全局最大的那批元素且有序。最终p2耗尽后nums1[0 ... p]剩余的元素在数值上一定小于等于已经放入的部分而且它们本身已经有序所以整体有序性成立。简单来说nums1的剩余元素等于“本来就在正确位置上的原住民”你去挪它们反而可能制造混乱。4.4 相等元素怎么处理稳定性有影响吗我在前面代码里用的是也就是当两个元素相等时优先把nums2的元素放入结果。这个选择对整型数组的排序结果没有影响因为两个相等的 2 在数组里无法区分最终数组仍然有序。但如果换成对象数组稳定性就可能重要。归并排序要求“相同元素的相对顺序不变”在合并两个子序列时一般会把左半边的元素先放入结果也就是用小等于号才稳定。如果你在 88 题这个场景里用了等价于把nums2的相等元素放在nums1相同元素前面这不符合稳定排序的习惯。不过这道题只是int[]稳定性没有任何意义。我更建议你在代码注释里写清楚“我刻意用了为的是优先消耗nums2”这样后面维护代码的人不会看不懂。4.5 数组特别大时方案三的优势更明显如果m和n都很大比如百万级以上方案二临时数组的分配是一个不小的时间开销而且还要额外遍历一次拷贝回nums1。方案三全程在nums1内部操作缓存访问也更友好。很多人在分析复杂度时只盯着大 O忽略了常数因子其实内存分配和两次遍历在真实场景中是有感的。当然如果数组大到nums1本身都无法放入内存那就需要外部归并排序的思路了和这道题的考察点完全不同这里不展开。5. 从这道题延伸出去的面试连环问5.1 链表版本合并两个有序链表面试官可能不会只满足于数组版本紧接着就会问“如果输入是两个有序链表怎么合并”。这题的思路依旧是双指针但链表没有预留尾部空间所以只能新建节点或者复用原有节点。迭代写法通常需要一个哨兵节点dummyHead来简化边界处理然后逐个比较两个链表的头节点把较小的节点接到结果链表的末尾。最后把剩余链表直接接上。时间复杂度O(mn)空间复杂度O(1)如果复用原有节点。链表和数组的核心区别在于数组可以用“倒着填”来避免覆盖链表则用“断开重接”来自然扩展。理解了 88 题的双指针思想再看链表版会轻松很多。5.2 K路归并与优先级队列LeetCode 有一道进阶题“合并K个升序链表”。解法有两种主流思路用小顶堆每次从 K 个链表中取出最小值或者两两合并。前者时间复杂度O(NlogK)后者如果每次都用线性合并总复杂度是O(NK)把两个两个的合并结果累积起来。如果你想从 88 题顺滑过渡到一个更大的体系可以先理解“合并两个有序序列”这个原子操作再看“多路归并”就只是重复调用而已。这也是分布式系统中外部排序的核心思想之一把大文件拆成多个有序片段再通过多路归并合成一个完整有序文件。5.3 面试官到底想通过这题看到什么这道题通常被安排在面试前半小时作为“热身题”或者“筛选题”。面试官重点想看三件事。第一你能不能准确理解题目条件。尤其是nums1预留了mn空间这个信息只要注意到它就说明你的阅读能力过关。第二你有没有空间复杂度意识。能想到从后往前、在O(1)额外空间内完成合并说明你平时写代码会考虑内存不是只会堆变量。第三你对边界条件的把握。m0、n0、p1变负数这些情况能不能处理干净直接反映代码基本功。所以这道题虽然叫 Easy但它考察的维度一点都不“简单”。我甚至觉得它比某些 Medium 题目更有面试价值。5.4 从这题出发理解归并排序的稳定性如果你之前写过归并排序可能对 merge 步骤有印象left[i]和right[j]比较如果left[i] right[j]放入left[i]否则放入right[j]。这样能保证相同的值在排序后保持原有顺序。88 题本质上也是一个 merge 步骤。区别在于它要求原地完成且右半部分输入在另一个数组里。如果你把 88 题写熟了再回头看归并排序的merge会觉得一切都是相通的既然nums1尾部有空间归并排序的一个子数组合并到另一个子数组时某些阶段也可以用倒序操作来节省临时空间虽然实际工程中很少这么干因为可读性会变差。但至少你有了“通过改变书写顺序来避免覆盖”的直觉。6. 一些刷题习惯上的小建议6.1 先画图再写代码别急着开局我给新人讲这道题时一定会让他们先在纸上画出两个数组用方框代表格子用箭头代表指针然后手动模拟几轮。这个过程看似麻烦但比直接看代码有效得多。画出指针移动过程后你会理解为什么p从最右边开始、为什么比较大的数放后面、为什么p1剩余不用管。以后遇到其他指针题比如移除元素、移动零、两数之和 II也可以先画图。算法题很多时候不是智商问题而是你有没有在脑内建立正确的动态模型。6.2 双指针模板怎么沉淀成自己的套路做完 88 题可以顺便把双指针归纳成几类相向双指针一个从头部、一个从尾部靠条件判断移动哪一个。比如两数之和、回文串判断。同向双指针两个指针都从头部出发一个快一个慢。比如去除有序数组的重复项。从后往前双指针本题属于这一类主要用于原地合并、原地调整顺序。滑动窗口本质上也是双指针两个边界不断移动。你能在 88 题里抽象出“从后往前填”这个模式下次遇到类似题目比如合并两个字符串的原地编辑题就能快速反应。6.3 做完题目后的三件套每次 AC 之后我建议再做三件事而不是急着看下一题。第一手动构造边界用例跑一遍。空数组、只有一个元素、全部元素相等、负数、m0或n0。这些用例最容易暴露隐藏 bug。第二把时间复杂度和空间复杂度口头说一遍。你要能在面试里一分钟内说清楚为什么是O(mn)而不是只说“因为用了双指针”。第三尝试用一句话概括思路。我自己的概括是“从后往前大数靠后谁大谁走。” 这句话能帮助你在遇到变体题时迅速唤醒记忆。最后分享一个我自己这几年刷题的小习惯。对于这种经典题我会每隔一段时间重新在白板上默写一遍不依赖 IDE 提示。默写过程会逼着我想清楚每一步的指针变化也能帮我发现自己是不是真的理解了还是只是记住了代码。88 题值得你这样做因为它的双指针倒序思路会贯穿很多后续的数组和链表题目。希望你也能从这道“简单题”里拿到一点不简单的收获。