Appearance
实战：合并两个有序数组
这道题也是双指针的应用，但有一个关键技巧：从后往前遍历。
这个技巧在很多原地修改的题目中都会用到。
题目描述
LeetCode 88. 合并两个有序数组
给你两个按非递减顺序排列的整数数组
nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你合并
nums2到nums1中，使合并后的数组同样按非递减顺序排列。
nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。
示例：
输入：nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出：[1, 2, 2, 3, 5, 6]题目分析
关键点：
- 两个数组都已排序：可以利用有序性
- 原地合并到 nums1：nums1 末尾有足够的空间
- 结果也要有序
思考一下：如果允许使用额外空间，怎么做？
归并排序的合并过程：用两个指针分别指向两个数组的开头，每次选较小的放入新数组。
但题目要求原地合并到 nums1。从前往后填充会有问题——会覆盖 nums1 中还没处理的元素。
怎么办？从后往前填充。
解法一：从前往后（需要额外空间）
先来看需要额外空间的解法，理解基本思路。
javascript
function merge(nums1, m, nums2, n) {
// 复制 nums1 的有效部分
const temp = nums1.slice(0, m);
let i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (temp[i] <= nums2[j]) {
nums1[k++] = temp[i++];
} else {
nums1[k++] = nums2[j++];
}
}
// 处理剩余元素
while (i < m) nums1[k++] = temp[i++];
while (j < n) nums1[k++] = nums2[j++];
}这是归并排序的经典合并过程。时间 O(m+n)，空间 O(m)。
但能不能不用额外空间？
解法二：从后往前（最优解）
关键观察：nums1 的末尾有 n 个空位，正好用来存放合并结果。
如果从后往前填充：
- 我们填充的位置在末尾
- nums1 的有效元素在开头
- 两者不会重叠！
javascript
function merge(nums1, m, nums2, n) {
let i = m - 1; // nums1 有效元素的末尾
let j = n - 1; // nums2 的末尾
let k = m + n - 1; // 填充位置，从末尾开始
// 从后往前比较并填充
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
// 如果 nums2 还有剩余
while (j >= 0) {
nums1[k--] = nums2[j--];
}
// nums1 剩余元素已经在正确位置，不用处理
}执行过程
以 nums1 = [1, 2, 3, 0, 0, 0], m=3, nums2 = [2, 5, 6], n=3 为例：
初始状态：
nums1: [1, 2, 3, 0, 0, 0]
↑ ↑
i=2 k=5
nums2: [2, 5, 6]
↑
j=2
第 1 步：比较 nums1[2]=3 和 nums2[2]=6
6 > 3，放 6 到 nums1[5]
[1, 2, 3, 0, 0, 6], j=1, k=4
第 2 步：比较 nums1[2]=3 和 nums2[1]=5
5 > 3，放 5 到 nums1[4]
[1, 2, 3, 0, 5, 6], j=0, k=3
第 3 步：比较 nums1[2]=3 和 nums2[0]=2
3 > 2，放 3 到 nums1[3]
[1, 2, 3, 3, 5, 6], i=1, k=2
第 4 步：比较 nums1[1]=2 和 nums2[0]=2
2 <= 2，放 nums2[0]=2 到 nums1[2]
[1, 2, 2, 3, 5, 6], j=-1, k=1
j < 0，nums2 处理完毕，结束。
nums1 剩余的 [1, 2] 已经在正确位置。
结果：[1, 2, 2, 3, 5, 6] ✓为什么不用处理 nums1 剩余元素？
当 nums2 处理完毕（j < 0）时，nums1 剩余的元素已经在它们应该在的位置上了。
因为我们是从后往前填充，nums1 的剩余元素在前面，填充的位置在后面，它们根本没有被动过。
但如果 nums1 先处理完（i < 0），nums2 还有剩余，那就需要继续把 nums2 的元素填进去。
复杂度分析：
- 时间复杂度：O(m + n)——每个元素最多被访问一次
- 空间复杂度：O(1)——只用了三个指针变量
常见错误
- 从前往后导致覆盖：这是最常见的错误
javascript
// 错误示范
function merge(nums1, m, nums2, n) {
let i = 0, j = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
i++; // 保持原位
} else {
// 想在 i 位置插入 nums2[j]...
// 但这会覆盖 nums1[i]！
}
}
}- 忘记处理 nums2 剩余元素
javascript
// 错误：只有主循环，没有处理剩余
function merge(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
// ...
}
// 如果 j >= 0，还有元素没处理！
}- 边界条件错误：指针的初始值和终止条件要仔细
相关题目
- 21. 合并两个有序链表：链表版本，思路类似
- 977. 有序数组的平方：也用到"从两端向中间"的双指针
本章小结
这一章我们学习了从后往前遍历的技巧：
- 问题：从前往后填充会覆盖未处理的元素
- 解决：从后往前填充，利用数组末尾的空间
- 关键：每次选两个数组末尾较大的元素放到最后
这个"从后往前"的思想很重要。当你遇到原地修改且可能覆盖的问题时，考虑反向遍历。
下一章，我们来看「旋转数组」。