1. 从一道简单题看双指针的实战价值LeetCode 88 题“合并两个有序数组”在题库里被标记为简单难度但我在过去几年带新人、做代码评审的过程中发现这道题能暴露出的问题一点都不简单。它表面上考的是数组合并实际上考的是你对原地操作、双指针从后往前遍历、边界条件处理这三个核心技能的理解深度。很多人第一次写这道题五分钟就能提交一个能通过的版本但如果你问他“为什么必须从后往前”“为什么不能用额外数组”“时间复杂度到底怎么算”能完整答上来的人不到三成。这篇文章适合三类人看第一类是刚刷 LeetCode 不久想通过一道题把双指针思想吃透的初学者第二类是刷了不少题但遇到原地合并类问题还是容易写挂的进阶者第三类是在准备面试需要把这道高频题讲清楚、写干净的求职者。我会从题目本身出发把思路拆解、代码实现、边界处理、常见错误、面试追问全部讲一遍让你做完这一道题就能举一反三拿下所有“两个有序序列合并”的变种题。先明确一下题目给你两个按非递减顺序排列的整数数组nums1和nums2以及两个整数m和n分别表示nums1和nums2中实际元素的个数。要求把nums2合并到nums1中使合并后的数组同样按非递减顺序排列。关键约束是最终结果不能通过返回新数组来实现必须原地修改nums1。nums1的长度是m n后n个位置预留给nums2的元素。这道题的核心关键词就是双指针、原地合并、从后往前、时间复杂度 O(mn)、空间复杂度 O(1)。下面我逐层拆开讲。2. 题目整体设计与思路拆解2.1 为什么不能从前往后直接合并最直觉的想法是这样的既然两个数组都是有序的那我从前往后比较谁小就把谁放到nums1的前面不就行了这个思路本身没错但问题在于nums1的前面已经有元素了。你从前往后遍历时一旦把nums2的元素插入到nums1的前面就会覆盖掉nums1中还没处理的元素。举个例子nums1 [1, 3, 5, 0, 0, 0]m 3nums2 [2, 4, 6]n 3。如果你从前往后比较第一步发现1 21不用动第二步发现2 3于是把2放到nums1[1]的位置结果原来的3就被覆盖了。你可能会说“那我先把nums1的前m个元素复制一份出来不就行了”——可以但那样空间复杂度就变成了 O(m)不是最优解。所以从前往后的核心矛盾是写入位置在读取位置之前会造成数据覆盖。要解决这个问题要么额外开空间要么换一个方向遍历。2.2 从后往前一个方向上的巧妙反转既然从前往后会覆盖未处理的数据那我们从后往前呢nums1的后n个位置是空的值为 0 的占位符我们可以把比较大的元素先放到数组末尾。这样一来写入位置始终在读取位置之后不会覆盖任何还没处理的元素。具体做法是用两个指针p1和p2分别指向nums1的第m-1个位置和nums2的第n-1个位置再用一个指针p指向nums1的最后一个位置mn-1。每次比较nums1[p1]和nums2[p2]把较大的那个放到nums1[p]然后对应的指针往前移动一位p也往前移动一位。重复这个过程直到其中一个数组处理完。这个思路的精妙之处在于它利用了nums1末尾的空闲空间把“合并”这个操作变成了“从大到小填充”。你不需要额外空间也不需要移动已有元素每个元素只被访问一次时间复杂度 O(mn)空间复杂度 O(1)。2.3 为什么这个思路是最优的从信息论的角度看合并两个有序数组至少需要访问每个元素一次所以时间复杂度下界就是 O(mn)从后往前的双指针正好达到了这个下界。空间方面题目已经给了nums1足够的空间如果我们还额外开数组那就是浪费。从后往前填充的做法完美利用了题目给的约束条件是真正意义上的最优解。我在面试中经常问的一个追问是“如果nums1的末尾没有预留空间你怎么办”这时候从后往前就不适用了你得先扩容或者开新数组。所以理解这个解法的适用前提很重要——它依赖于nums1有足够的尾部空间。3. 核心细节解析与实操要点3.1 三个指针的初始位置与移动逻辑三个指针的初始化非常关键写错一个就容易数组越界p1 m - 1指向nums1中最后一个有效元素p2 n - 1指向nums2中最后一个有效元素p m n - 1指向nums1的最后一个位置也就是合并后数组的末尾循环的条件是p1 0 p2 0也就是说两个数组都还有元素没处理完。在循环体内比较nums1[p1]和nums2[p2]如果nums1[p1] nums2[p2]把nums1[p1]放到nums1[p]然后p1--、p--否则把nums2[p2]放到nums1[p]然后p2--、p--这里有一个细节当两个元素相等时我们选择先放nums1的元素。这不会影响结果的正确性因为相等的元素谁先谁后都一样。但从稳定性角度考虑虽然这道题不要求稳定先放nums1的元素可以保证nums1中原本靠后的相等元素仍然靠后。3.2 循环结束后的收尾处理循环结束后有两种情况第一种是p1 0说明nums1的元素已经全部处理完但nums2还有剩余。这时候需要把nums2中剩下的元素依次复制到nums1的前面。为什么因为nums2剩下的元素都是比已经放置的元素更小的它们应该排在nums1的最前面。第二种是p2 0说明nums2的元素已经全部处理完但nums1还有剩余。这时候不需要做任何操作因为nums1剩下的元素本来就在正确的位置上——它们比已经放置的所有元素都小而且已经在nums1的前面了。很多初学者会忘记处理第一种情况导致nums2中较小的元素丢失。我建议在写代码时循环结束后统一加一个while (p2 0)的收尾循环把nums2剩余元素搬过去。这样写虽然多了一个循环但逻辑更清晰不容易出错。3.3 边界条件的全面梳理这道题的边界条件不少我整理了一个表格方便你对照检查边界情况具体场景处理要点m 0nums1没有有效元素直接把nums2全部复制到nums1n 0nums2没有元素不需要任何操作直接返回m 0且n 0两个数组都为空直接返回不做任何处理nums1元素全部大于nums2如nums1[4,5,6]nums2[1,2,3]从后往前比较时nums2的元素会先被放置最后nums1的元素留在原位nums2元素全部大于nums1如nums1[1,2,3]nums2[4,5,6]nums1的元素先被放置到末尾nums2的元素最后通过收尾循环复制到前面存在重复元素如nums1[1,2,2]nums2[2,3]相等时先放nums1的元素保证结果正确提示在本地测试时建议至少覆盖上面表格中的每一种情况。尤其是m 0和n 0这两种极端情况很多人写代码时只考虑了“两个数组都有元素”的常规场景一提交就挂在这些边界上。4. 实操过程与核心环节实现4.1 完整代码实现与逐行注释下面给出 Python 和 Java 两个版本的实现都是可以直接复制到 LeetCode 上提交的。Python 版本class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: Do not return anything, modify nums1 in-place instead. # 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 前面 # 如果 nums1 还有剩余不需要处理它们已经在正确位置 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]; p1--; } else { nums1[p] nums2[p2]; p2--; } p--; } // 只需要处理 nums2 剩余的情况 while (p2 0) { nums1[p] nums2[p2]; p2--; p--; } } }4.2 执行过程逐步推演拿一个具体的例子走一遍你就明白每一步在干什么了。输入nums1 [1, 3, 5, 0, 0, 0]m 3nums2 [2, 4, 6]n 3初始状态p1 2指向 5p2 2指向 6p 5指向最后一个 0步骤比较操作数组状态指针变化15 vs 66 更大放到nums1[5][1,3,5,0,0,6]p21, p425 vs 45 更大放到nums1[4][1,3,5,0,5,6]p11, p333 vs 44 更大放到nums1[3][1,3,5,4,5,6]p20, p243 vs 23 更大放到nums1[2][1,3,3,4,5,6]p10, p151 vs 22 更大放到nums1[1][1,2,3,4,5,6]p2-1, p0循环结束p2 -1收尾循环不执行。最终结果[1,2,3,4,5,6]正确。再看一个需要收尾的例子nums1 [4, 5, 6, 0, 0, 0]m 3nums2 [1, 2, 3]n 3步骤比较操作数组状态指针变化16 vs 36 更大放到nums1[5][4,5,6,0,0,6]p11, p425 vs 35 更大放到nums1[4][4,5,6,0,5,6]p10, p334 vs 34 更大放到nums1[3][4,5,6,4,5,6]p1-1, p2循环结束p1 -1但p2 2还有元素。收尾循环把nums2[0..2]依次复制到nums1[0..2]最终得到[1,2,3,4,5,6]。4.3 复杂度分析与参数选择时间复杂度每个元素最多被访问一次循环总共执行m n次所以是O(mn)。这个复杂度已经是最优的因为任何合并算法都必须至少读取每个元素一次。空间复杂度只用了三个指针变量没有开辟任何与输入规模相关的额外空间所以是O(1)。有读者可能会问“Python 里nums1[p] nums1[p1]这种赋值算不算额外空间”不算这只是常数级别的临时变量不随输入规模变化。空间复杂度的核心是看有没有开辟与m或n成正比的内存。注意有些语言比如 Python的列表切片操作nums1[:] sorted(nums1[:m] nums2)虽然写起来短但空间复杂度是 O(mn)不符合题目的原地要求。面试时如果这么写面试官大概率会追问“能不能优化到 O(1)”。5. 常见问题与排查技巧实录5.1 高频错误速查表我在代码评审和面试中见过太多人在这道题上翻车下面这张表整理了最常见的错误和对应的排查方法错误现象根本原因排查方法修复方案数组越界指针初始值写错比如p1 m而不是m-1打印指针初始值检查是否在[0, m-1]范围内统一用m-1和n-1初始化结果中nums2的小元素丢失忘记处理循环结束后的收尾检查循环结束后p2是否大于等于 0加while p2 0收尾循环结果顺序不对比较时用了而不是或者方向搞反用[1,2,2]和[2,3]这种有重复的用例测试相等时先放nums1的元素覆盖了未处理的元素从前往后遍历检查遍历方向改为从后往前m0时结果为空没有单独处理m0的情况用nums1[0]m0nums2[1]测试收尾循环会自动处理确认循环条件正确提交后提示“修改了输入数组但结果不对”在函数内重新赋值了nums1而不是原地修改检查是否有nums1 ...这样的语句用索引赋值nums1[p] ...5.2 三个我踩过的坑第一个坑指针初始值写成m和n。刚开始刷题时我总觉得“第 m 个元素”就是索引 m结果一提交就数组越界。后来养成了一个习惯凡是涉及数组索引的先在纸上画一遍标清楚每个指针指向哪个元素确认无误再写代码。第二个坑以为循环结束后不需要收尾。我最早写的版本只处理了两个数组都有元素的情况测试用例nums1[4,5,6,0,0,0]、nums2[1,2,3]直接挂了。后来我总结了一个规律从后往前合并时只需要检查第二个数组是否还有剩余因为第一个数组的剩余元素天然就在正确位置。这个规律帮我省了很多调试时间。第三个坑在 Python 里用nums1 nums1[:m] nums2然后sort。这样写确实能过但完全违背了题目的原地要求。面试时如果这么写面试官会认为你没有理解题目的核心考点。后来我强制自己只用索引赋值再也不走捷径。5.3 面试追问与应对策略这道题在面试中经常被用作“热身题”但面试官往往会在此基础上追问。我整理了几个常见的追问和应对思路追问一“如果nums1的末尾没有预留空间你怎么合并”这时候从后往前就不适用了。你可以先计算合并后的长度扩容nums1然后再从后往前填充。或者如果允许返回新数组直接开一个新数组用从前往后的双指针合并。追问二“如果两个数组是降序的怎么改”降序的话从后往前比较时应该放较小的元素到末尾或者改成从前往后比较、从后往前填充。核心思想不变只是比较逻辑反过来。追问三“这个算法稳定吗”稳定排序的定义是相等元素的相对顺序不变。在这道题中当nums1[p1] nums2[p2]时我们先放nums1的元素所以nums1中的相等元素会排在nums2中相等元素的后面。如果要求稳定应该先放nums2的元素。不过这道题不要求稳定所以两种写法都可以。追问四“能不能用二分查找优化”对于两个有序数组的合并二分查找并不能降低时间复杂度因为最终还是要移动所有元素。二分查找适合在单个有序数组中查找不适合合并场景。如果题目改成“在一个有序数组中插入另一个数组的元素”二分查找才有用武之地。6. 从这道题延伸出的通用解题框架6.1 双指针从后往前的适用场景这道题的核心技巧是“从后往前双指针”它适用于所有原地合并两个有序序列的场景。判断能不能用这个技巧看两个条件第一目标数组有足够的尾部空间第二两个源序列都是有序的。满足这两个条件就可以放心用从后往前的双指针。类似的题目还有“合并两个有序链表”不过链表没有“从后往前”的概念所以用的是从前往后的双指针。数组和链表的区别在于数组可以随机访问所以能从后往前链表只能顺序访问所以只能从前往后。理解这个区别你就能根据数据结构的特点选择合适的遍历方向。6.2 原地操作的通用原则原地操作的核心原则是写入位置不能覆盖还没读取的数据。从前往后写入会覆盖后面的数据从后往前写入会覆盖前面的数据。所以选择遍历方向时要看哪边的数据是“安全”的。在这道题中nums1的后半部分是空的所以从后往前写入是安全的。这个原则可以推广到很多原地操作场景比如“原地删除数组中的重复元素”“原地移除指定元素”等。这些题目通常用从前往后的双指针因为写入位置在读取位置之前不会覆盖未处理的数据。6.3 举一反三三道变种题变种一合并两个有序数组但要求去重。在比较时如果nums1[p1] nums2[p2]只放一个另一个跳过。收尾时也要注意去重。变种二合并 K 个有序数组。可以用最小堆优先队列来做每次从 K 个数组中取出最小的元素。时间复杂度 O(N log K)其中 N 是所有元素的总数。变种三两个有序数组求交集。用双指针从前往后遍历相等就加入结果不相等就移动较小的那个指针。时间复杂度 O(mn)空间复杂度 O(min(m,n))。这三道变种题都可以在 LeetCode 上找到对应的题目做完 88 题之后可以顺手练一下把双指针的套路彻底吃透。6.4 刷题方法论的几点体会最后分享几点我在刷题过程中总结的方法论。第一不要追求刷题数量要追求刷题质量。一道 88 题吃透比刷十道同类型的题但每道都一知半解要强。第二每道题至少写两遍。第一遍看题解理解思路第二遍关掉题解独立写出来第三遍尝试优化和变种。第三建立自己的错题本。把每次踩的坑记下来定期回顾避免重复犯错。这道 88 题我前前后后写了不下十遍每次都有新的体会。从最开始只会从前往后硬写到后来理解从后往前的精妙再到能给别人讲清楚每一步的原理这个过程本身就是一种成长。刷题不是为了背答案而是为了训练思维方式。当你能把一道简单题讲出深度你就真正掌握了它。 
长河君 · 2026/10/20 12:23:21 · 阅读 1.2k LeetCode 88 双指针原地合并有序数组：从后往前遍历与边界处理
1. 从一道简单题看双指针的实战价值LeetCode 88 题“合并两个有序数组”在题库里被标记为简单难度但我在过去几年带新人、做代码评审的过程中发现这道题能暴露出的问题一点都不简单。它表面上考的是数组合并实际上考的是你对原地操作、双指针从后往前遍历、边界条件处理这三个核心技能的理解深度。很多人第一次写这道题五分钟就能提交一个能通过的版本但如果你问他“为什么必须从后往前”“为什么不能用额外数组”“时间复杂度到底怎么算”能完整答上来的人不到三成。这篇文章适合三类人看第一类是刚刷 LeetCode 不久想通过一道题把双指针思想吃透的初学者第二类是刷了不少题但遇到原地合并类问题还是容易写挂的进阶者第三类是在准备面试需要把这道高频题讲清楚、写干净的求职者。我会从题目本身出发把思路拆解、代码实现、边界处理、常见错误、面试追问全部讲一遍让你做完这一道题就能举一反三拿下所有“两个有序序列合并”的变种题。先明确一下题目给你两个按非递减顺序排列的整数数组nums1和nums2以及两个整数m和n分别表示nums1和nums2中实际元素的个数。要求把nums2合并到nums1中使合并后的数组同样按非递减顺序排列。关键约束是最终结果不能通过返回新数组来实现必须原地修改nums1。nums1的长度是m n后n个位置预留给nums2的元素。这道题的核心关键词就是双指针、原地合并、从后往前、时间复杂度 O(mn)、空间复杂度 O(1)。下面我逐层拆开讲。2. 题目整体设计与思路拆解2.1 为什么不能从前往后直接合并最直觉的想法是这样的既然两个数组都是有序的那我从前往后比较谁小就把谁放到nums1的前面不就行了这个思路本身没错但问题在于nums1的前面已经有元素了。你从前往后遍历时一旦把nums2的元素插入到nums1的前面就会覆盖掉nums1中还没处理的元素。举个例子nums1 [1, 3, 5, 0, 0, 0]m 3nums2 [2, 4, 6]n 3。如果你从前往后比较第一步发现1 21不用动第二步发现2 3于是把2放到nums1[1]的位置结果原来的3就被覆盖了。你可能会说“那我先把nums1的前m个元素复制一份出来不就行了”——可以但那样空间复杂度就变成了 O(m)不是最优解。所以从前往后的核心矛盾是写入位置在读取位置之前会造成数据覆盖。要解决这个问题要么额外开空间要么换一个方向遍历。2.2 从后往前一个方向上的巧妙反转既然从前往后会覆盖未处理的数据那我们从后往前呢nums1的后n个位置是空的值为 0 的占位符我们可以把比较大的元素先放到数组末尾。这样一来写入位置始终在读取位置之后不会覆盖任何还没处理的元素。具体做法是用两个指针p1和p2分别指向nums1的第m-1个位置和nums2的第n-1个位置再用一个指针p指向nums1的最后一个位置mn-1。每次比较nums1[p1]和nums2[p2]把较大的那个放到nums1[p]然后对应的指针往前移动一位p也往前移动一位。重复这个过程直到其中一个数组处理完。这个思路的精妙之处在于它利用了nums1末尾的空闲空间把“合并”这个操作变成了“从大到小填充”。你不需要额外空间也不需要移动已有元素每个元素只被访问一次时间复杂度 O(mn)空间复杂度 O(1)。2.3 为什么这个思路是最优的从信息论的角度看合并两个有序数组至少需要访问每个元素一次所以时间复杂度下界就是 O(mn)从后往前的双指针正好达到了这个下界。空间方面题目已经给了nums1足够的空间如果我们还额外开数组那就是浪费。从后往前填充的做法完美利用了题目给的约束条件是真正意义上的最优解。我在面试中经常问的一个追问是“如果nums1的末尾没有预留空间你怎么办”这时候从后往前就不适用了你得先扩容或者开新数组。所以理解这个解法的适用前提很重要——它依赖于nums1有足够的尾部空间。3. 核心细节解析与实操要点3.1 三个指针的初始位置与移动逻辑三个指针的初始化非常关键写错一个就容易数组越界p1 m - 1指向nums1中最后一个有效元素p2 n - 1指向nums2中最后一个有效元素p m n - 1指向nums1的最后一个位置也就是合并后数组的末尾循环的条件是p1 0 p2 0也就是说两个数组都还有元素没处理完。在循环体内比较nums1[p1]和nums2[p2]如果nums1[p1] nums2[p2]把nums1[p1]放到nums1[p]然后p1--、p--否则把nums2[p2]放到nums1[p]然后p2--、p--这里有一个细节当两个元素相等时我们选择先放nums1的元素。这不会影响结果的正确性因为相等的元素谁先谁后都一样。但从稳定性角度考虑虽然这道题不要求稳定先放nums1的元素可以保证nums1中原本靠后的相等元素仍然靠后。3.2 循环结束后的收尾处理循环结束后有两种情况第一种是p1 0说明nums1的元素已经全部处理完但nums2还有剩余。这时候需要把nums2中剩下的元素依次复制到nums1的前面。为什么因为nums2剩下的元素都是比已经放置的元素更小的它们应该排在nums1的最前面。第二种是p2 0说明nums2的元素已经全部处理完但nums1还有剩余。这时候不需要做任何操作因为nums1剩下的元素本来就在正确的位置上——它们比已经放置的所有元素都小而且已经在nums1的前面了。很多初学者会忘记处理第一种情况导致nums2中较小的元素丢失。我建议在写代码时循环结束后统一加一个while (p2 0)的收尾循环把nums2剩余元素搬过去。这样写虽然多了一个循环但逻辑更清晰不容易出错。3.3 边界条件的全面梳理这道题的边界条件不少我整理了一个表格方便你对照检查边界情况具体场景处理要点m 0nums1没有有效元素直接把nums2全部复制到nums1n 0nums2没有元素不需要任何操作直接返回m 0且n 0两个数组都为空直接返回不做任何处理nums1元素全部大于nums2如nums1[4,5,6]nums2[1,2,3]从后往前比较时nums2的元素会先被放置最后nums1的元素留在原位nums2元素全部大于nums1如nums1[1,2,3]nums2[4,5,6]nums1的元素先被放置到末尾nums2的元素最后通过收尾循环复制到前面存在重复元素如nums1[1,2,2]nums2[2,3]相等时先放nums1的元素保证结果正确提示在本地测试时建议至少覆盖上面表格中的每一种情况。尤其是m 0和n 0这两种极端情况很多人写代码时只考虑了“两个数组都有元素”的常规场景一提交就挂在这些边界上。4. 实操过程与核心环节实现4.1 完整代码实现与逐行注释下面给出 Python 和 Java 两个版本的实现都是可以直接复制到 LeetCode 上提交的。Python 版本class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: Do not return anything, modify nums1 in-place instead. # 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 前面 # 如果 nums1 还有剩余不需要处理它们已经在正确位置 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]; p1--; } else { nums1[p] nums2[p2]; p2--; } p--; } // 只需要处理 nums2 剩余的情况 while (p2 0) { nums1[p] nums2[p2]; p2--; p--; } } }4.2 执行过程逐步推演拿一个具体的例子走一遍你就明白每一步在干什么了。输入nums1 [1, 3, 5, 0, 0, 0]m 3nums2 [2, 4, 6]n 3初始状态p1 2指向 5p2 2指向 6p 5指向最后一个 0步骤比较操作数组状态指针变化15 vs 66 更大放到nums1[5][1,3,5,0,0,6]p21, p425 vs 45 更大放到nums1[4][1,3,5,0,5,6]p11, p333 vs 44 更大放到nums1[3][1,3,5,4,5,6]p20, p243 vs 23 更大放到nums1[2][1,3,3,4,5,6]p10, p151 vs 22 更大放到nums1[1][1,2,3,4,5,6]p2-1, p0循环结束p2 -1收尾循环不执行。最终结果[1,2,3,4,5,6]正确。再看一个需要收尾的例子nums1 [4, 5, 6, 0, 0, 0]m 3nums2 [1, 2, 3]n 3步骤比较操作数组状态指针变化16 vs 36 更大放到nums1[5][4,5,6,0,0,6]p11, p425 vs 35 更大放到nums1[4][4,5,6,0,5,6]p10, p334 vs 34 更大放到nums1[3][4,5,6,4,5,6]p1-1, p2循环结束p1 -1但p2 2还有元素。收尾循环把nums2[0..2]依次复制到nums1[0..2]最终得到[1,2,3,4,5,6]。4.3 复杂度分析与参数选择时间复杂度每个元素最多被访问一次循环总共执行m n次所以是O(mn)。这个复杂度已经是最优的因为任何合并算法都必须至少读取每个元素一次。空间复杂度只用了三个指针变量没有开辟任何与输入规模相关的额外空间所以是O(1)。有读者可能会问“Python 里nums1[p] nums1[p1]这种赋值算不算额外空间”不算这只是常数级别的临时变量不随输入规模变化。空间复杂度的核心是看有没有开辟与m或n成正比的内存。注意有些语言比如 Python的列表切片操作nums1[:] sorted(nums1[:m] nums2)虽然写起来短但空间复杂度是 O(mn)不符合题目的原地要求。面试时如果这么写面试官大概率会追问“能不能优化到 O(1)”。5. 常见问题与排查技巧实录5.1 高频错误速查表我在代码评审和面试中见过太多人在这道题上翻车下面这张表整理了最常见的错误和对应的排查方法错误现象根本原因排查方法修复方案数组越界指针初始值写错比如p1 m而不是m-1打印指针初始值检查是否在[0, m-1]范围内统一用m-1和n-1初始化结果中nums2的小元素丢失忘记处理循环结束后的收尾检查循环结束后p2是否大于等于 0加while p2 0收尾循环结果顺序不对比较时用了而不是或者方向搞反用[1,2,2]和[2,3]这种有重复的用例测试相等时先放nums1的元素覆盖了未处理的元素从前往后遍历检查遍历方向改为从后往前m0时结果为空没有单独处理m0的情况用nums1[0]m0nums2[1]测试收尾循环会自动处理确认循环条件正确提交后提示“修改了输入数组但结果不对”在函数内重新赋值了nums1而不是原地修改检查是否有nums1 ...这样的语句用索引赋值nums1[p] ...5.2 三个我踩过的坑第一个坑指针初始值写成m和n。刚开始刷题时我总觉得“第 m 个元素”就是索引 m结果一提交就数组越界。后来养成了一个习惯凡是涉及数组索引的先在纸上画一遍标清楚每个指针指向哪个元素确认无误再写代码。第二个坑以为循环结束后不需要收尾。我最早写的版本只处理了两个数组都有元素的情况测试用例nums1[4,5,6,0,0,0]、nums2[1,2,3]直接挂了。后来我总结了一个规律从后往前合并时只需要检查第二个数组是否还有剩余因为第一个数组的剩余元素天然就在正确位置。这个规律帮我省了很多调试时间。第三个坑在 Python 里用nums1 nums1[:m] nums2然后sort。这样写确实能过但完全违背了题目的原地要求。面试时如果这么写面试官会认为你没有理解题目的核心考点。后来我强制自己只用索引赋值再也不走捷径。5.3 面试追问与应对策略这道题在面试中经常被用作“热身题”但面试官往往会在此基础上追问。我整理了几个常见的追问和应对思路追问一“如果nums1的末尾没有预留空间你怎么合并”这时候从后往前就不适用了。你可以先计算合并后的长度扩容nums1然后再从后往前填充。或者如果允许返回新数组直接开一个新数组用从前往后的双指针合并。追问二“如果两个数组是降序的怎么改”降序的话从后往前比较时应该放较小的元素到末尾或者改成从前往后比较、从后往前填充。核心思想不变只是比较逻辑反过来。追问三“这个算法稳定吗”稳定排序的定义是相等元素的相对顺序不变。在这道题中当nums1[p1] nums2[p2]时我们先放nums1的元素所以nums1中的相等元素会排在nums2中相等元素的后面。如果要求稳定应该先放nums2的元素。不过这道题不要求稳定所以两种写法都可以。追问四“能不能用二分查找优化”对于两个有序数组的合并二分查找并不能降低时间复杂度因为最终还是要移动所有元素。二分查找适合在单个有序数组中查找不适合合并场景。如果题目改成“在一个有序数组中插入另一个数组的元素”二分查找才有用武之地。6. 从这道题延伸出的通用解题框架6.1 双指针从后往前的适用场景这道题的核心技巧是“从后往前双指针”它适用于所有原地合并两个有序序列的场景。判断能不能用这个技巧看两个条件第一目标数组有足够的尾部空间第二两个源序列都是有序的。满足这两个条件就可以放心用从后往前的双指针。类似的题目还有“合并两个有序链表”不过链表没有“从后往前”的概念所以用的是从前往后的双指针。数组和链表的区别在于数组可以随机访问所以能从后往前链表只能顺序访问所以只能从前往后。理解这个区别你就能根据数据结构的特点选择合适的遍历方向。6.2 原地操作的通用原则原地操作的核心原则是写入位置不能覆盖还没读取的数据。从前往后写入会覆盖后面的数据从后往前写入会覆盖前面的数据。所以选择遍历方向时要看哪边的数据是“安全”的。在这道题中nums1的后半部分是空的所以从后往前写入是安全的。这个原则可以推广到很多原地操作场景比如“原地删除数组中的重复元素”“原地移除指定元素”等。这些题目通常用从前往后的双指针因为写入位置在读取位置之前不会覆盖未处理的数据。6.3 举一反三三道变种题变种一合并两个有序数组但要求去重。在比较时如果nums1[p1] nums2[p2]只放一个另一个跳过。收尾时也要注意去重。变种二合并 K 个有序数组。可以用最小堆优先队列来做每次从 K 个数组中取出最小的元素。时间复杂度 O(N log K)其中 N 是所有元素的总数。变种三两个有序数组求交集。用双指针从前往后遍历相等就加入结果不相等就移动较小的那个指针。时间复杂度 O(mn)空间复杂度 O(min(m,n))。这三道变种题都可以在 LeetCode 上找到对应的题目做完 88 题之后可以顺手练一下把双指针的套路彻底吃透。6.4 刷题方法论的几点体会最后分享几点我在刷题过程中总结的方法论。第一不要追求刷题数量要追求刷题质量。一道 88 题吃透比刷十道同类型的题但每道都一知半解要强。第二每道题至少写两遍。第一遍看题解理解思路第二遍关掉题解独立写出来第三遍尝试优化和变种。第三建立自己的错题本。把每次踩的坑记下来定期回顾避免重复犯错。这道 88 题我前前后后写了不下十遍每次都有新的体会。从最开始只会从前往后硬写到后来理解从后往前的精妙再到能给别人讲清楚每一步的原理这个过程本身就是一种成长。刷题不是为了背答案而是为了训练思维方式。当你能把一道简单题讲出深度你就真正掌握了它。