企业官网建设流程全解析

刷算法题的时候，每次看到“求两个有序数组的中位数”，我第一反应是先确认一件事：数组真的有序吗？只要数组有序，这道题就不再是“排序”问题，而是“如何利用有序性做文章”的问题。今天要聊的双指针归并法，是所有解法里最容易理解、也最不容易写错的一种，尤其适合刚开始接触这道题的人当入门模板。

它的核心思路一句话就能说清：像拉拉链一样，按从小到大的顺序把两个数组的元素逐个“放”出来，然后停在正中间的位置，根据总长度是奇数还是偶数，决定是取一个数还是取两个数求平均。整个过程不需要把两个数组真的完整合并，也不需要额外开一个大数组，只需要两个指针加一个计数变量就够了。

这篇文章我会把逻辑拆成三步讲透，附上一份可以直接跑通的 Java 实现代码，再把空数组、奇偶长度、指针越界这些容易翻车的细节逐个过一遍。如果你是面试准备阶段，把它当作标准模板来用；如果你已经刷过这道题，也建议重新审视一下“指针到底该在什么时机停”，因为很多错误版本恰恰是栽在这个看似不起眼的地方。

1. 问题剖析与整体思路拆解

1.1 这道题到底在考什么

先明确题目本身：给定两个升序排列的整数数组 nums1 和 nums2，比如[1, 3]和[2]，要求返回它们合并后的中位数。这里“合并后”不是说真的要新建一个数组，而是指把两个数组的所有元素放在一起，按大小排列后的中间值。

中位数的定义本身有两个需要注意的细节：

• 如果元素总数是奇数，比如[1, 2, 3]，中位数就是正中间那个 2。
• 如果元素总数是偶数，比如[1, 2, 3, 4]，中位数是中间两个数的平均值，也就是 (2 + 3) / 2 = 2.5。

这两个细节直接决定了代码里循环要执行多少次、最后要返回什么。很多人的代码在奇数长度下能跑通，一到偶数长度就多取了一个数或者少取了一个数，根因就是没有把奇数、偶数两种情况在循环结束后的状态想清楚。

这道题在面试中的定位也很明确：它不像动态规划或者图论那样需要复杂的解题模型，但它同时考察了几个基础能力——对数组指针的掌控、对循环终止条件的推导、对时间复杂度的敏感度。面试官很可能会在此基础上追问“能不能做到 O(log(m+n))”，这属于后续优化话题，但先把双指针归并法吃透，等于把地基打牢了。

1.2 为什么先选双指针归并而不是直接排序合并

第一次见到这道题的人，最容易想到的方案是：把 nums1 和 nums2 放进一个新的数组，然后调用Arrays.sort()，最后按下标取中位数。这种写法确实简单，三五行代码就能跑通测试用例。

但问题在于两点：

1. 两个数组本身已经有序，你却把它们混合后重新排序，等于把已知信息白白浪费了。排序的时间复杂度至少是 O((m+n)log(m+n))，完全可以用 O(m+n) 的归并思想做到线性时间。
2. 这种做法需要额外开辟一个长度为 m+n 的结果数组，空间复杂度是 O(m+n)。而双指针归并法在适当优化后，空间复杂度可以降到 O(1)。

打个生活化的比方：你手里有两副已经按身高排好队的照片，现在要找出所有人里最高的那三分之一。正常做法是直接把两摞照片倒在一起重新排序，而双指针归并的做法是让两摞照片各出来一个人比身高，矮的进结果集，高的留下继续比。后者每一步只比较两个人，完全不用把全体重新洗牌，效率自然更高。

1.3 双指针归并法和二分法怎么选

刷过这道题的人应该知道，还存在一种基于“第 K 小元素”思想的二分法，时间复杂度可以压到 O(log(min(m, n)))。我个人的建议是：第一遍学的时候先掌握双指针归并，再考虑二分法。

原因有两个：

• 双指针归并的思路直观，代码逻辑清晰，适合作为理解题意的起点。只要你能解释清楚指针为什么这样移动，边界条件为什么这样处理，面试时就能拿到基础分。
• 二分法是优化版本，它对人称“很难一次写对”，因为要处理分割位置、左边最大值与右边最小值的比较、奇偶长度的统一公式等，代码量更大，心智负担更高。如果没有双指针归并打底，直接上二分法很容易把自己绕晕。

两种方法的时间复杂度对比也很明显：

如果面试官没有特别要求时间复杂度，双指针归并完全够用；如果明确要求 O(log(m+n))，那就要切换到二分法。这篇文章先把双指针归并讲到透彻，后面我会在第五节给二分法做一次简明拆解，方便你按需选择。

2. 三步法核心逻辑详解

2.1 第一步：用双指针把两个有序数组归并起来

“双指针归并”这个名字听起来有点唬人，本质就是把两个指针分别指向两个数组的起点，然后反复比较它们指向的元素，谁小谁就“胜出”。

具体做法是：

1. 指针 i 初始指向 nums1 的第一个元素，指针 j 初始指向 nums2 的第一个元素。
2. 比较 nums1[i] 和 nums2[j]。
3. 如果 nums1[i] 小于等于 nums2[j]，就“取走” nums1[i]，随后 i 向后移动一位。
4. 否则“取走” nums2[j]，随后 j 向后移动一位。
5. 重复以上过程，直到把两个数组的元素都取完。

这个过程和“合并两个有序链表”的套路几乎一模一样。区别在于本题不需要真的把所有元素存进新数组，只需要在归并过程中记录某些特定位置的元素值。

为什么要强调“不需要完整归并”呢？因为中位数只和中间位置的元素有关，你只需要把归并过程推进到中间位置，自然就得到了答案。这就好比从一副扑克牌里抽中间那张牌，没必要把整副牌一张张翻完。

2.2 第二步：根据总长度奇偶性确定中位数的位置

假设 nums1 的长度是 m，nums2 的长度是 n，总长度 totalLen = m + n。

• 如果 totalLen 是奇数，比如 5，那中位数是合并后第 3 个元素（按人类计数法），换成数组下标就是 index = totalLen / 2 = 2。
• 如果 totalLen 是偶数，比如 6，那中位数是合并后第 3 个元素和第 4 个元素的平均值，对应数组下标是 index = totalLen / 2 - 1 = 2 和 index = totalLen / 2 = 3。

但这里有一个实现层面的陷阱：如果只用一个循环来推进指针，当循环结束时，你可能只知道“当前取到的元素”和“上一次取到的元素”，这两个值是否正好对应偶数情况下需要的两个中间数？答案是：只要循环次数设置得正确，它们恰好就对应上了。

我常用的循环次数是 totalLen / 2 + 1。为什么是这个数？因为不管总数是奇数还是偶数，中位数的“候选位置”最多覆盖到第 totalLen / 2 个下标，而为了取到偶数情况下的前一个值，我们必须在推进指针的过程中始终保留上一次取到的值。多循环一次，就能保证最终停下来时：

• current 保存的是第 totalLen / 2 个元素。
• previous 保存的是第 totalLen / 2 - 1 个元素。

这样一来：

• 奇数长度：直接返回 current。
• 偶数长度：返回 (previous + current) / 2.0。

很多文章直接用“走到第 k 个元素”的说法，但总是把 k 的来源讲得很含糊。我习惯把这个 k 拆成 totalLen / 2 + 1，也就是循环总次数，这样写代码时不容易出错。

2.3 第三步：在归并过程中只记录需要的结果，不完整合并

完整归并两个数组需要遍历所有 m+n 个元素，但找中位数只需要遍历到第 totalLen / 2 个元素。所以实际的循环次数只需要 totalLen / 2 + 1 次。

每轮循环做的事情是：

1. 从当前两个指针指向的元素里，选较小的那个作为本轮“取到的元素”。
2. 把“本轮元素”保存为 current，同时把上一轮的 current 保存为 previous，为偶数情况做准备。
3. 移动被选中那一侧的指针。
4. 如果某一侧数组已经取完，就固定从另一侧继续取。

举个例子：nums1 = [1, 2, 3]，nums2 = [4, 5, 6]，totalLen = 6，循环次数 = 6 / 2 + 1 = 4。前四轮取到的元素依次是 1、2、3、4，循环结束时 previous = 3，current = 4，返回 (3 + 4) / 2.0 = 3.5。这正好是合并数组[1, 2, 3, 4, 5, 6]的中位数。

这样操作的好处非常直观：时间复杂度从 O(m+n) 降到了 O((m+n)/2)，虽然渐进意义下还是 O(m+n)，但实际运行时间少了一半。更重要的是，我们不需要额外数组保存归并结果，空间复杂度是严格的 O(1)。

3. Java 代码实现与逐步讲解

3.1 完整可运行的示例代码

先上一份可以直接跑通的 Java 代码，然后再逐段拆解。

public class MedianOfTwoSortedArrays { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int totalLen = m + n; int i = 0; // nums1 的指针 int j = 0; // nums2 的指针 int previous = 0; // 记录上一轮取到的元素 int current = 0; // 记录当前轮取到的元素 // 只需要遍历到中间位置 int loopCount = totalLen / 2 + 1; for (int count = 0; count < loopCount; count++) { // 先把上一轮的 current 移动到 previous previous = current; // 决定当前轮取哪个数组的元素 if (i < m && (j >= n || nums1[i] <= nums2[j])) { current = nums1[i]; i++; } else { current = nums2[j]; j++; } } // 奇数长度：直接返回 current if ((totalLen & 1) == 1) { return current; } // 偶数长度：返回中间两个数的平均值 return (previous + current) / 2.0; } public static void main(String[] args) { MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays(); int[] nums1 = new int[]{1, 3}; int[] nums2 = new int[]{2}; System.out.println(solution.findMedianSortedArrays(nums1, nums2)); // 2.0 int[] nums3 = new int[]{1, 2}; int[] nums4 = new int[]{3, 4}; System.out.println(solution.findMedianSortedArrays(nums3, nums4)); // 2.5 int[] nums5 = new int[]{0, 0}; int[] nums6 = new int[]{0, 0}; System.out.println(solution.findMedianSortedArrays(nums5, nums6)); // 0.0 } }

运行结果：

2.0 2.5 0.0

3.2 关键代码行逐段拆解

这份代码真正核心的就三个部分：指针选择逻辑、循环次数、奇偶判断。我逐个展开。

第一处：指针选择逻辑

if (i < m && (j >= n || nums1[i] <= nums2[j])) { current = nums1[i]; i++; } else { current = nums2[j]; j++; }

这段最容易被绕晕。我拆开讲：

• j >= n表示 nums2 已经取完了，此时无论 nums1[i] 是多少，都必须从 nums1 取。
• i < m表示 nums1 还没取完。如果 nums1 取完了，这个条件为 false，整个 if 不成立，代码会走到 else，从 nums2 继续取。
• nums1[i] <= nums2[j]是正常的比较逻辑，因为两个数组都是升序，取小的那个才能保证整体归并有序。

简而言之，这个条件顺序是：先判断 nums1 能不能取，再判断 nums2 是否已经空，最后才是值比较。这里有多种写法，比如先判断j >= n再判断i >= m，但无论怎么写，核心原则是：不要让指针越界，不要让任何一个数组没有取完却被跳过。

第二处：循环次数

int loopCount = totalLen / 2 + 1; for (int count = 0; count < loopCount; count++) { ... }

为什么不是 totalLen / 2？因为偶数情况下需要两个中间数。比如 totalLen = 4，中间两个数的下标是 1 和 2，循环次数 4 / 2 + 1 = 3，也就是三轮。三轮结束后 previous 对应下标 1，current 对应下标 2。如果只循环 2 次，previous 对应下标 0，current 对应下标 1，得到的结果就完全错了。

第三处：奇偶判断

if ((totalLen & 1) == 1) { return current; } return (previous + current) / 2.0;

totalLen & 1是按位与运算，用来判断最低位是否为 1，等价于totalLen % 2 == 1。奇数时只有一个中间元素，直接返回 current；偶数时返回两个中间元素平均值。

我特别提醒一点：除以 2.0 而不是 2，否则整数相加再除以整数，结果会被截断成整数。这是 Java 里最容易踩的类型转换坑。

3.3 几个容易写错的实现细节

第一处容易错的是把 previous 和 current 的赋值顺序搞反。有的人会先更新 current 再更新 previous，结果 previous 永远保存的是“当前轮的前一轮的前一轮”的值，偶数结果直接错。我自己的经验是把previous = current;放在每次循环开头，保证它在任何情况下都是上一轮的值。

第二处容易错的是 while 条件里把“取完”的数组漏掉。如果某个数组已经取完，而你还去访问它的元素，就会触发数组下标越界。上面代码里j >= n这个条件就是用来兜底的。

第三处容易错的是用new int[]测试时，忘了区分数组长度为零的情况。虽然 LeetCode 上两个数组不会同时为空，但面试时手写代码很可能遇到边界测试，最好在开头主动处理：如果 nums1 为空，直接对 nums2 求中位数；如果 nums2 为空，直接对 nums1 求中位数。这样既省时间，也不容易出错。

4. 边界条件与常见问题排查实录

4.1 空数组怎么处理

面试官经常在写完主逻辑后问：“如果其中一个数组是空的，你的代码还能跑吗？”答案是可以跑，但取决于你有没有写兜底分支。

建议在方法开始处增加如下判断：

if (m == 0) { return medianOfSingleArray(nums2); } if (n == 0) { return medianOfSingleArray(nums1); }

其中的 single array 求中位数逻辑很简单：如果长度是奇数，返回中间元素；如果是偶数，返回中间两个元素的平均值。写成独立方法可以复用，也不会污染主流程。

有了这个兜底，主流程里虽然依然有i < m和j >= n这类判断，但真实情况下不会出现同时为空或者某一侧完全为空导致指针完全不动的情况，代码的健壮性会好很多。

4.2 奇偶长度验证

我习惯在写完代码后手算几个典型用例，这里分享我的验证清单：

最后一个用例值得多说一句：nums1 只有一个元素，nums2 有三个元素，totalLen = 4，循环次数 = 4 / 2 + 1 = 3。三轮分别取到 1、2、3，previous = 2，current = 3，返回 2.5，完全正确。

4.3 指针移动时最常见的三个坑

第一个坑：while 条件写成while (i < m || j < n)，然后循环体里不限制循环次数。这样会把整个数组走完，虽然结果可能也对，但效率上多做了无用功，而且不符合“三步搞定”的简洁思路。

第二个坑：在分支判断时，先写nums1[i] < nums2[j]，然后 else 里直接nums2[j]，完全不考虑边界。只要一边数组取完，立刻越界。正确做法是把“是否取完”的判断放在最前面，或者用短路条件把越界风险挡在外面。

第三个坑：偶数情况下，previous 没有在正确时机更新。我见过不少版本把 previous 的赋值放在循环末尾，结果 previous 变成 current 的旧值，也就是当前元素，而不是前一个元素。这种错误最隐蔽，因为奇数用例完全看不出问题，只有偶数用例的答案会偏差 0.5。

4.4 面试官可能追问的后续问题

写完这道题，面试官大概率会继续问：

• 时间复杂度是多少？回答 O(m+n)，并解释清楚为什么是 m+n 而不是 m*n。
• 空间复杂度呢？回答 O(1)，因为只用了常数额外变量。
• 能不能再快一点？这就要引出二分法了。
• 如果数组里有重复元素怎么办？我们的解法天然支持重复元素，因为只比较值的大小，不会因为相等就跳过元素。

如果你把上面这些点都能自然接上，面试官会认为你不只是背代码，而是真的理解了归并的本质。

5. 进一步优化：从双指针归并到二分查找

5.1 为什么 O(m+n) 在某些场景下还不够

力扣原题的要求是时间复杂度要达到 O(log(m+n))。双指针归并虽然空间占用优秀，但时间是线性的，在 m 和 n 非常大的时候，比如各一千万个元素，线性遍历要跑约一千万次，而二分法只需要几十次比较。这个差距在数据规模变大后会非常明显。

从面试角度讲，O(m+n) 是及格线，O(log(m+n)) 是加分项。如果你还有余力，建议补上二分法；如果时间紧张，先保证双指针归并完全不出错。

5.2 二分法的核心思路简述

二分法的本质是“在较短的那个数组上做分割”，而不是逐个比较元素。

假设我们在某个较短数组上确定一个分割位置，那么长数组上的分割位置可以由“总分割数量减去短数组的分割数量”直接算出来。这样就把两个数组各分割成左右两部分。只要满足：

• 短数组左侧最大值 <= 长数组右侧最小值
• 长数组左侧最大值 <= 短数组右侧最小值

那么整体的分割就是正确的，中位数就能直接从分割线左右四个数里算出。如果不满足，就根据比较结果调整短数组的分割位置，用二分法快速逼近。

这个思路理解起来比双指针归并难不少，主要难在分割位置变化时，需要同步维护“左半边元素个数等于右半边元素个数”或“左半边比右半边多一个”这两个全局约束。

5.3 双指针归并还是二分法：怎么选

如果只是为了通过常规模拟面试，双指针归并的代码量更少、出错率更低。如果面试官特别要求 O(log(m+n))，就必须上二分法。

我个人建议的掌握顺序是：先独立写出双指针归并版本，并能清楚解释每一行代码存在的理由；再去看二分法，把它当作一道新的题目来训练。两个版本都掌握之后，你对“有序数组”这类题型的理解会上一个台阶，后续遇到“寻找第 K 小的数”“两个有序数组的 Top K”等变体也会顺手不少。

6. 扩展思考：归并思想还能用在哪里

双指针归并法不只是这一道题的解法。它本质上是一种“利用局部有序性做线性合并”的通用技巧，在很多场景都能用到：

• 合并两个有序链表，这是链表题里最基础的题型之一。思路和数组双指针完全一致，只是把索引移动换成了节点移动。
• 求两个有序数组的交集。同样用双指针，相等则记录，否则小数指针前进。
• 求两个有序数组的第 K 小元素。可以基于双指针归并做剪枝，也可以用二分法直接定位。
• 海量数据外排序中的归并阶段。当数据量大到无法全部加载进内存时，先把大文件切分并排序，再用“多路归并”逐段合成整体有序结果。这里的思想依然是双指针，只是从两路扩展到了多路。

所以今天花时间写清楚这一个算法，收获的不仅是一道题的答案，更是一整套“有序结构合并”的操作范式。

我个人在实际写代码时最有体感的经验是：这种线性归并的题，最怕的就是“边界处理靠感觉”。每一次循环之前，先在纸上把指针能走到的最远位置画出来，再写代码，基本就不会错。另一个小技巧是，在写循环体之前先在注释里写清楚“循环结束时 previous 和 current 分别代表哪两个位置的元素”，写完注释后再补代码，思路会清晰非常多。最后再分享一个我踩过几次的坑：无论题目描述得多复杂，先确认两个数组是不是真的有序。如果无序，双指针归并的前提就不成立，必须重新设计整体思路。这个前置检查看起来废话，却能省下大把调试时间。