1. 从一道简单题看双指针的实战价值LeetCode 88 题“合并两个有序数组”在题库里被标记为简单难度但我在过去几年带新人、做代码审查的过程中发现这道题能暴露出的问题远比想象中多。它表面上考的是数组合并实际上考的是你对原地操作、逆向双指针、边界条件这三件事的理解深度。很多人第一次写这道题五分钟就能提交一个能通过的版本但如果你问他“为什么必须从后往前填”大概率会卡住。这篇文章适合三类人正在刷题但想搞懂每道题背后思维模型的人、面试前需要快速回顾高频手写题的人、以及写了几年业务代码但发现基础算法手感退化的人。我会从题目本身出发把双指针的底层逻辑、逆向遍历的数学原因、不同解法的取舍、以及实际面试中面试官真正想听到的东西全部拆开讲清楚。读完你不仅能默写出最优解还能在面试官追问“能不能优化空间”的时候给出有说服力的回答。这道题的核心关键词是有序数组、原地合并、双指针、逆向填充、时间复杂度 O(mn)。把这几个词吃透你就能把同一套思维迁移到归并排序的 merge 步骤、链表合并、以及很多需要“从后往前处理”的场景里。2. 题目拆解与核心约束分析2.1 题目到底给了什么条件先把题目用大白话复述一遍。给你两个数组nums1和nums2它们都是非递减有序的。nums1的长度是m n其中前m个元素是有效数据后n个位置是占位的 0专门留给nums2的元素填进来。nums2的长度是n里面全是有效数据。要求你把nums2合并进nums1最终nums1是一个包含mn个元素的有序数组。关键约束有三个每一个都直接影响解法选择原地修改不能新建一个数组返回必须直接改nums1。这就排除了“新建数组再拷贝”的偷懒做法。有序性两个数组各自有序这是双指针能成立的前提。如果无序就只能排序复杂度直接变成 O((mn)log(mn))。nums1 尾部有空洞后n个位置是空的这个细节是整道题的题眼。很多人忽略它导致写出需要额外空间或者需要移动元素的笨解法。2.2 为什么“简单”标签容易让人掉以轻心我见过太多人看到“简单”两个字扫一眼题目就开始写。最常见的错误写法是这样的新建一个result数组然后用两个指针从头比较谁小放谁最后把result拷回nums1。这个解法逻辑上没错时间复杂度也是 O(mn)但空间复杂度是 O(mn)而且完全没利用“nums1尾部有空洞”这个条件。面试官出这道题不是想看你能否合并两个数组而是想看你能否在有限空间内优雅地完成合并。如果你上来就开新数组面试官会认为你没有认真读题或者没有养成优化空间的意识。这就是“简单题”的陷阱它简单到你能快速写出一个能跑的版本但写出最优版本需要你对指针方向有清晰判断。2.3 正向双指针的死胡同在哪里正向双指针的思路是i指向nums1开头j指向nums2开头比较nums1[i]和nums2[j]把小的那个放到结果里。问题在于如果你直接往nums1的前面填会覆盖掉还没比较的元素。举个例子nums1 [1, 3, 5, 0, 0, 0]nums2 [2, 4, 6]。i0指向 1j0指向 21 更小本来 1 就应该在位置 0不用动。接着i1指向 3j0指向 22 更小如果直接把 2 写到nums1[1]那原来的 3 就被覆盖了而 3 还没参与比较。这就是正向填充的根本矛盾写入位置永远落后于或等于读取位置覆盖不可避免。要解决这个矛盾要么额外开空间暂存要么换方向。换方向就是逆向双指针的起点。3. 逆向双指针从后往前填的数学直觉3.1 为什么从后往前就不会覆盖逆向双指针的核心操作是用三个指针p1 m - 1指向nums1最后一个有效元素p2 n - 1指向nums2最后一个元素p m n - 1指向nums1最后一个位置。每次比较nums1[p1]和nums2[p2]把大的那个放到nums1[p]然后对应指针减一。为什么这样不会覆盖因为p永远大于等于p1。p的初始值是mn-1p1的初始值是m-1差值正好是n。每次往nums1[p]写入时p指向的位置要么是空洞初始的 0要么是已经被处理过的位置。而p1指向的位置永远在p的左边还没被写入过。所以写入操作永远不会覆盖p1还没读取的数据。用生活化的类比你有两摞已经按大小排好的扑克牌要合并成一摞。如果从最小的开始拿你得先把小牌抽出来放到一边因为桌面空间不够。但如果从最大的开始拿你可以直接把大牌放到最终牌堆的底部因为底部本来就是空的不会压到还没拿的牌。逆向双指针就是这个“从最大开始拿”的策略。3.2 指针移动的完整逻辑具体步骤拆解初始化p1 m - 1p2 n - 1p m n - 1。当p1 0且p2 0时循环执行如果nums1[p1] nums2[p2]说明nums1当前最大的元素更大把它放到nums1[p]然后p1--。否则把nums2[p2]放到nums1[p]然后p2--。每次写入后p--。循环结束后如果p2 0说明nums2还有剩余元素没放完需要继续把nums2[0..p2]依次拷贝到nums1[0..p]。如果p1 0而p2 0不需要做任何事因为nums1剩下的元素本来就在正确位置上。这里有一个容易被忽略的细节循环结束后只需要处理nums2的剩余元素不需要处理nums1的剩余元素。原因很简单nums1剩下的元素已经在数组的前部它们的位置本来就是对的。而nums2剩下的元素必须搬过去。3.3 时间与空间复杂度分析时间复杂度是 O(mn)因为每个元素最多被访问和写入一次。空间复杂度是 O(1)只用了三个指针变量没有额外数组。这是这道题能达到的最优解。对比其他解法解法时间复杂度空间复杂度是否原地面试推荐度新建数组正向双指针O(mn)O(mn)否低先拼接再排序O((mn)log(mn))O(1)是低正向双指针临时数组O(mn)O(m)半原地中逆向双指针O(mn)O(1)是高从表格能看出来逆向双指针在时间和空间两个维度都达到了最优而且完全符合“原地修改”的要求。这就是为什么它是标准答案。4. 代码实现与逐行注释4.1 Python 版本def merge(nums1, m, nums2, n): # p1 指向 nums1 最后一个有效元素 p1 m - 1 # p2 指向 nums2 最后一个元素 p2 n - 1 # p 指向 nums1 最后一个位置填充位置 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 # 如果 nums2 还有剩余直接拷贝到前面 # nums1 有剩余则不用处理因为它们已经在正确位置 while p2 0: nums1[p] nums2[p2] p2 - 1 p - 1这段代码有几个值得注意的写法细节。第一else分支同时处理了nums1[p1] nums2[p2]的情况包括相等的情况。相等时放哪个都可以放nums2的元素可以保证稳定性如果考虑稳定性的话。第二最后的while p2 0不能写成while p2 0因为p2 0时还有一个元素没放。第三不需要写while p1 0的收尾循环原因前面已经解释过。4.2 Java 版本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]; p1--; } else { nums1[p] nums2[p2]; p2--; } p--; } while (p2 0) { nums1[p] nums2[p2]; p2--; p--; } }Java 版本和 Python 版本逻辑完全一致只是语法不同。Java 里数组是定长的nums1的长度在传入时就已经是mn所以直接下标赋值即可。4.3 边界情况的手动推演光看代码不够我习惯把几个典型边界情况手动跑一遍确认指针变化符合预期。情况一nums2 为空n0nums1 [1,2,3]m3nums2 []n0。p12p2-1p2。主循环条件p2 0不成立直接跳过。收尾循环也不成立。数组不变正确。情况二nums1 有效部分为空m0nums1 [0,0,0]m0nums2 [1,2,3]n3。p1-1p22p2。主循环条件p1 0不成立跳过。收尾循环把nums2从后往前拷贝到nums1最终nums1 [1,2,3]正确。情况三nums1 所有元素都比 nums2 大nums1 [4,5,6,0,0,0]m3nums2 [1,2,3]n3。第一轮nums1[2]6 nums2[2]3nums1[5]6p11p4。第二轮nums1[1]5 nums2[2]3nums1[4]5p10p3。第三轮nums1[0]4 nums2[2]3nums1[3]4p1-1p2。主循环结束。收尾循环把nums2的[1,2,3]依次放到nums1[2]、nums1[1]、nums1[0]最终nums1 [1,2,3,4,5,6]正确。情况四nums2 所有元素都比 nums1 大nums1 [1,2,3,0,0,0]m3nums2 [4,5,6]n3。第一轮nums1[2]3 nums2[2]6nums1[5]6p21p4。第二轮nums1[2]3 nums2[1]5nums1[4]5p20p3。第三轮nums1[2]3 nums2[0]4nums1[3]4p2-1p2。主循环结束。收尾循环不执行。最终nums1 [1,2,3,4,5,6]正确。这四个边界情况覆盖了 n0、m0、以及两个极端的相对大小关系。手动推演一遍比单纯看代码更能建立信心。5. 面试现场面试官真正想听什么5.1 从暴力解到最优解的沟通过程面试的时候最忌讳的是上来就写最优解一句话不说。面试官更想看到你的思考过程。我通常建议的沟通节奏是这样的先确认理解“我理解题目要求把 nums2 合并到 nums1 里nums1 后面有足够的空位最终结果要有序而且不能开新数组对吗”这一步能避免你理解错题意白写半天。然后给出暴力思路“最直接的做法是新建一个数组用两个指针从头比较谁小放谁最后拷贝回去。时间 O(mn)空间 O(mn)。”这一步展示你有基本的解题能力。接着指出优化点“但题目说 nums1 后面有空位而且要求原地修改所以我想能不能利用这些空位。如果从后往前比较把大的元素先放到 nums1 的末尾就不会覆盖还没处理的数据。”这一步是加分项展示你读懂了题目的隐含条件。最后写代码“我用三个指针p1 指向 nums1 有效部分的末尾p2 指向 nums2 的末尾p 指向 nums1 的最后一个位置……”边写边解释写完再手动跑一个例子验证。5.2 高频追问与应对面试官常见的追问有三个追问一“为什么从后往前就不会覆盖”回答要点因为写入位置 p 永远大于等于读取位置 p1p 指向的要么是空洞要么是已处理过的位置而 p1 指向的是还没读取的有效数据所以不会覆盖。追问二“如果 nums1 后面没有空位怎么办”回答要点那就必须开新数组或者先把 nums1 的元素整体后移 n 位但后移的时间复杂度是 O(m)整体还是 O(mn)只是多了一次移动操作。不过题目已经给了空位所以不需要考虑这种情况。追问三“这个算法稳定吗”回答要点当 nums1[p1] nums2[p2] 时代码里放的是 nums2 的元素所以 nums2 中相等的元素会排在 nums1 中相等元素的后面。如果要求稳定性这个行为需要明确。不过对于这道题稳定性通常不是考察点。5.3 手写代码时的常见扣分点我做过几次模拟面试官发现候选人在手写这道题时最容易犯的错误有收尾循环写成while p2 0漏掉最后一个元素。忘记在每次写入后p--导致所有元素都写到同一个位置。主循环条件写成while p1 0 and p2 0漏掉下标 0 的元素。比较时用而不是导致相等时行为不一致虽然不影响正确性但逻辑上不够清晰。写完不验证直接说“好了”面试官会认为你缺乏自测习惯。这些细节看起来小但在面试场景下每一个都可能成为扣分项。我的建议是写完代码后至少手动跑一个包含相等元素的例子比如nums1 [1,2,3,0,0,0]nums2 [2,5,6]确认输出是[1,2,2,3,5,6]。6. 从这道题延伸出的实战思维6.1 归并排序的 merge 步骤LeetCode 88 本质上就是归并排序中 merge 操作的简化版。归并排序的 merge 步骤通常需要额外 O(n) 空间因为两个子数组都不带空洞。但如果你在归并排序的某些变体中能够保证其中一个子数组尾部有足够空间就可以用同样的逆向双指针技巧做到 O(1) 额外空间。这个思维在外部排序中特别有用。比如你要合并两个已经排好序的大文件内存放不下全部数据但你可以从文件末尾开始读取把大的元素先写到输出文件的末尾。这样就不需要额外的磁盘空间来暂存结果。6.2 链表合并的异同合并两个有序链表LeetCode 21和这道题经常被放在一起对比。链表合并用的是正向双指针因为链表节点不需要连续内存你可以直接改变指针指向不存在覆盖问题。而数组是连续内存正向填充会覆盖所以需要逆向。这个对比能帮你理解“数据结构决定算法策略”这个核心思想。6.3 其他需要逆向处理的场景逆向思维在算法题里出现的频率比想象中高。比如字符串反转从后往前交换字符。数组轮转先整体反转再局部反转。删除有序数组中的重复项有时候从后往前处理能避免元素移动。接雨水问题从两边向中间逼近本质上也是一种逆向思维。这些场景的共同点是正向处理会遇到覆盖、移动或者状态依赖的问题而逆向处理能把这些麻烦消解掉。养成“先想想能不能从后往前”的习惯能让你在遇到新题时多一条思路。7. 常见问题与排查技巧实录7.1 提交报错速查表报错类型典型原因排查方法答案错误收尾循环条件写错检查while p2 0是否漏掉下标 0答案错误指针减一遗漏检查每次写入后p--是否执行答案错误比较符号写反确认nums1[p1] nums2[p2]时放 nums1 的元素索引越界p1 或 p2 初始值错误确认p1 m - 1p2 n - 1超时用了排序解法检查是否误用了sort()应该用双指针空间超限新建了数组检查是否创建了额外的 list 或 array7.2 我踩过的三个坑第一个坑是收尾循环的方向。我一开始写收尾循环的时候下意识地从前往后拷贝nums2的剩余元素结果发现顺序反了。因为nums2剩余的元素是较小的那些它们应该放在nums1的前部而且要保持原有顺序。从后往前拷贝正好能保证顺序正确。第二个坑是相等元素的处理。我一开始用后来改成发现结果不一样。具体来说当nums1[p1] nums2[p2]时如果放nums1的元素那么nums2中相等的元素会被放到更前面可能破坏稳定性。虽然这道题不考察稳定性但养成明确的处理习惯很重要。第三个坑是忘记处理 m0 的情况。当nums1没有有效元素时p1 -1主循环直接跳过收尾循环负责把所有nums2的元素搬过去。如果收尾循环写错了这种情况就会报错。我后来养成了一个习惯写完代码后至少手动跑一遍 m0 和 n0 的情况。7.3 一个容易被忽略的优化点虽然逆向双指针已经是时间 O(mn)、空间 O(1) 的最优解但在实际工程中如果nums2的最小元素比nums1的最大元素还大那么nums2的所有元素都应该直接追加到nums1后面不需要逐个比较。这个优化在数据分布有偏的时候能减少比较次数但在面试中通常不需要提因为最坏情况复杂度没变。不过如果你在面试中主动提到这个优化面试官会觉得你对性能有敏感度。你可以这样说“如果 nums2[0] nums1[m-1]说明 nums2 的所有元素都大于 nums1 的有效元素直接拷贝即可不需要逐个比较。不过这个优化不改变最坏情况复杂度所以不是必须的。”8. 刷题之外的收获这道题我前前后后给不同的人讲过不下二十遍每次都能发现新的细节。它教会我的最重要的一件事是不要被“简单”标签迷惑每道题都值得认真对待。很多所谓的简单题背后藏着的思维模型可以迁移到更复杂的场景里。逆向双指针这个技巧我在处理日志合并、时间区间合并、以及某些数据库的 merge join 实现中都见过类似的思想。另一个收获是沟通和代码同样重要。面试的时候面试官不仅看你写出的代码更看你如何思考、如何解释、如何验证。同样的算法有人讲得清清楚楚有人写得对但说不明白结果可能完全不同。我建议你在刷题的时候养成“自言自语”的习惯把每一步的理由说出来这样到了面试现场才不会卡壳。最后分享一个我个人的练习方法每刷完一道题合上编辑器用白纸把代码默写一遍然后手动跑三个测试用例。如果三个都过了这道题才算真正掌握。这个方法很笨但效果很好。LeetCode 88 我默写过至少十遍现在闭着眼睛都能写出正确的指针初始化和循环条件。这种肌肉记忆在面试的高压环境下能救你一命。