企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文围绕《AlgoNote 算法通关手册》中的 0088. 合并两个有序数组题解 展开，系统讲解如何在不开辟新数组的前提下，将两个有序数组合并为一个有序数组。文章先完整还原题目约束与两个标准示例，再深入拆解「从后向前」的双指针逆序归并思路，并结合仓库中的归并排序源码、链表归并实现与双指针专题文档，阐明该解法与归并排序「合并过程」的底层血缘关系。读完本文，你将掌握双指针归并在数组原地合并场景下的核心套路，并能随手写出可运行、可 AC 的 Python 解法。

题目链接

• 0088. 合并两个有序数组 - 力扣（LeetCode）
• 本题在仓库中的完整题解：docs/solutions/0001-0099/merge-sorted-array.md

题目大意

描述：给定两个有序数组 $nums1$、$nums2$。

要求：将 $nums2$ 合并到 $nums1$ 中，使 $nums1$ 成为一个有序数组。

说明：

• 给定数组 $nums1$ 的空间大小为 $m + n$，其中前 $m$ 个位置存放的是 $nums1$ 的元素（末尾 $n$ 个位置是留给合并用的空位）。$nums2$ 的空间大小为 $n$。这样可以用 $nums1$ 自身的空间来存储最终的有序数组，做到原地合并。
• $nums1.length == m + n$。
• $nums2.length == n$。
• $0 \le m, n \le 200$。
• $1 \le m + n \le 200$。
• $-10^9 \le nums1[i], nums2[j] \le 10^9$。

示例：

• 示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6]。 合并结果是 [1,2,2,3,5,6]，其中斜体加粗标注的为 nums1 中的元素。

• 示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 []。 合并结果是 [1]。

本题与仓库中的另一道简单题「0021. 合并两个有序链表」是同一归并思想的「数组版」与「链表版」，可对照学习。

解题思路

思路 1：双指针从后向前逆序归并

思路分析

直接套用归并排序中「两个有序子数组合并」的常规做法——从前往后比较——在这里会遇到一个麻烦：$nums1$ 的有效元素占据数组前 $m$ 个位置，若从前向后把 $nums2$ 中的较小元素插入到 $nums1$ 前部，会覆盖尚未比较的 $nums1$ 元素，因此常规做法需要额外开辟一个大小为 $m + n$ 的辅助数组，空间复杂度为 $O(m + n)$。

题目特意把 $nums1$ 的长度设置为 $m + n$，末尾预留了 $n$ 个空位，就是引导我们从后向前归并：两个数组最大的元素一定放在整个结果数组的最后面，而从后向前写入时，写的是数组末尾的空位，永远不会覆盖 $nums1$ 中还没处理完的有效元素，因此可以完全原地完成。

具体步骤如下：

1. 初始化三个指针：$index1$ 指向 $nums1$ 有效元素的最后一个位置（$m - 1$），$index2$ 指向 $nums2$ 的最后一个位置（$n - 1$），$index$ 指向 $nums1$ 数组的末尾（$m + n - 1$），作为写入位置。
2. 从后向前循环比较 $nums1[index1]$ 与 $nums2[index2]$ 的大小：谁大就把谁写入 $nums1[index]$，同时对应的指针左移；每写入一个元素，$index$ 也左移一位。
3. 循环终止时，可能有两种情况：
   • $nums2$ 中还有剩余元素：此时 $index2 \ge 0$，直接把 $nums2$ 剩余部分整体拷贝到 $nums1$ 前面对应位置（因为它们必然是最小的几个元素，且已有序）。
   • $nums1$ 中还有剩余元素：无需处理，它们本来就已经在自己的位置上。

用 $nums1 = [1,2,3,0,0,0], m = 3,\ nums2 = [2,5,6], n = 3$ 走一遍：

当 $index2$ 变为 $-1$、$nums2$ 全部处理完毕时，$nums1$ 中的剩余元素 $[1]$ 天然就在正确位置，无需移动，合并完成。

思路 1：代码

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: # 三个指针分别指向 nums1 有效区末尾、nums2 末尾、nums1 数组末尾 index1 = m - 1 index2 = n - 1 index = m + n - 1 # 从后向前比较，较大的元素写入 nums1 末尾的空位 while index1 >= 0 and index2 >= 0: if nums1[index1] < nums2[index2]: nums1[index] = nums2[index2] index2 -= 1 else: nums1[index] = nums1[index1] index1 -= 1 index -= 1 # nums2 若还有剩余元素（都是最小的一批），直接拷贝到 nums1 前部 nums1[:index2 + 1] = nums2[:index2 + 1]

思路 1：复杂度分析

• 时间复杂度：$O(m + n)$。$index1$ 与 $index2$ 每轮至少有一个左移一位，两个指针总共移动 $m + n$ 次，末尾的切片拷贝最多再消耗 $O(n)$，总体为 $O(m + n)$。
• 空间复杂度：$O(1)$。代码没有开辟任何新数组，只使用了常数个指针变量，是真正的原地归并。原题解中标注的 $O(m + n)$ 对应的是「从前往后合并、需要额外辅助数组」的朴素做法；采用逆序双指针后，额外空间可降为 $O(1)$，这也是本题面试考察的核心优化点。

边界情况与易错点

1. $n = 0$：$nums2$ 为空，while循环直接跳过，nums1[:1]的切片也不会覆盖任何元素，函数直接返回，$nums1$ 保持原样。
2. $m = 0$：$nums1$ 前部没有有效元素，此时index1 = -1，循环不进入，nums1[:index2 + 1] = nums2[:index2 + 1]会把 $nums2$ 整体拷贝到 $nums1$ 中，正好完成合并。
3. 相等元素的处理：比较时使用<（nums1[index1] < nums2[index2]才取 $nums2$ 的元素，否则取 $nums1$ 的），相等时优先保留 $nums1$ 的元素。归并本身是稳定操作，两个数组中相等的元素先后顺序不会被打乱。
4. 切片赋值：nums1[:index2 + 1] = nums2[:index2 + 1]利用了 Python 列表的切片赋值特性，原地修改 $nums1$ 的前index2 + 1个位置，无需写循环。

深度拓展：与仓库源码中归并思想的对应关系

1. 归并排序「合并过程」的数组版

本题的双指针归并，本质上就是归并排序中「合并两个有序子数组」这一核心步骤的特化版本。仓库中 数组归并排序实现 的merge方法展示了标准写法：两个指针left_i、right_i分别从两个有序子数组头部出发，比较后把较小元素追加到结果数组，直到某一侧耗尽，再把另一侧剩余元素全部追加：

def merge(self, left_nums: [int], right_nums: [int]): nums = [] left_i, right_i = 0, 0 while left_i < len(left_nums) and right_i < len(right_nums): if left_nums[left_i] < right_nums[right_i]: nums.append(left_nums[left_i]) left_i += 1 else: nums.append(right_nums[right_i]) right_i += 1 while left_i < len(left_nums): nums.append(left_nums[left_i]) left_i += 1 while right_i < len(right_nums): nums.append(right_nums[right_i]) right_i += 1 return nums

对比可见，本题的逆序归并只是把「较小者先写入」翻转成「较大者先写入」，并借助 $nums1$ 末尾预留的空位省掉了辅助数组。归并排序的完整思路与复杂度分析可参考仓库文档 docs/01_array/01_07_array_merge_sort.md：归并排序总体时间复杂度 $O(n \log n)$、空间复杂度 $O(n)$，其合并步骤单次即 $O(m + n)$，与本题单次合并的复杂度一致。

2. 链表版的同源解法

同样的「双指针归并」思路在链表中体现为 0021. 合并两个有序链表：通过哑节点dummy_head串联两条链，每次取较小值的节点接入结果链，最后把剩余链整体接上。仓库中 链表归并排序实现 的merge方法即该思想的直接复用：

def merge(self, left, right): dummy_head = ListNode(-1) cur = dummy_head while left and right: if left.val <= right.val: cur.next = left left = left.next else: cur.next = right right = right.next cur = cur.next if left: cur.next = left elif right: cur.next = right return dummy_head.next

数组与链表的差异只在「内存连续性」：数组可以靠下标 $O(1)$ 随机访问任意位置，因此能逆序从尾部向前写入；链表只能顺序移动指针，因而从头部开始用哑节点串联。两道题合在一起，恰好覆盖了双指针归并的两种主要形态。

3. 本题在仓库知识体系中的定位

在 双指针专题文档 中，双指针被分为「对撞指针」「快慢指针」「分离双指针」三类。本题属于分离双指针的变体：两个指针分别作用在两个数组上（$index1$ 作用在 $nums1$，$index2$ 作用在 $nums2$），协同完成有序数组合并。仓库的分类题目列表 docs/00_preface/00_06_categories_list.md 也将本题标记为「数组、双指针、排序」标签，难度为简单，是双指针入门阶段强烈推荐的练习。

延伸思考：从这道题还能学到什么

1. 就地操作（in-place）的价值：当题目允许原地修改输入、且输入本身就预留了空间时，优先考虑利用这些空间，将空间复杂度从 $O(m + n)$ 压到 $O(1)$。本题是这一优化最典型的教科书案例。
2. 逆序遍历规避覆盖问题：前向遍历会覆盖未处理元素时，反向思考——从尾部开始、把较大元素往末尾放——往往能巧妙绕开。类似思路也出现在数组原地移动类问题中。
3. 归并是高频基本功：合并两个有序数组/链表是归并排序、外部排序、合并 K 个有序序列（对应仓库题解 merge-k-sorted-lists.md）等众多算法的最小组件，值得彻底吃透。

总结

LeetCode 88「合并两个有序数组」用一道简单题承载了两个高频考点：双指针归并与原地就地操作。核心解法是从后向前双指针逆序归并，时间复杂度 $O(m + n)$，空间复杂度 $O(1)$。它与仓库中数组归并排序的merge过程、链表归并的实现同出一源，掌握了它，就掌握了归并家族算法的入口。

• 教程
• 文档
• 知识库