LeetCode 373. 查找和最小的K对数字——多路归并与优先队列的优化

适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约20分钟 | 难度：中等

---

开篇故事

上一篇讲了合并K个链表的「K路归并」，这道题是「K路归并」思想的另一个经典应用。

两个有序数组，各取一个元素配对，找和最小的 K 对。乍一看跟合并K链表没什么关系，但如果你把「每个 nums1[i] 与 nums2 的配对」看成一条虚拟的「链表」，就会发现：(nums1[0], nums2[0]), (nums1[0], nums2[1]), ... 是一个递增的有序序列，(nums1[1], nums2[0]), (nums1[1], nums2[1]), ... 也是。我们要从这 m 条虚拟链表中，按顺序取出前 K 个最小的对。

这就是标准的多路归并，优先队列完美适配。

---

一、题目解析

题目描述：

给定两个以升序排列的整数数组 nums1 和 nums2，以及一个整数 k。定义一对值 (u, v)，其中第一个元素来自 nums1，第二个元素来自 nums2。请找到和最小的 k 个数对。

示例：

输入：nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出：[[1,2],[1,4],[1,6]]

约束：

• 1 <= nums1.length, nums2.length <= 10^5
• 1 <= k <= 10^4

---

二、解法一：枚举所有对然后排序

思路分析

枚举所有 m × n 个数对，排序后取前 K 个。

import java.util.*;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        List<int[]> allPairs = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                allPairs.add(new int[]{nums1[i], nums2[j]});
            }
        }
        
        allPairs.sort((a, b) -> (a[0] + a[1]) - (b[0] + b[1]));
        
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < Math.min(k, allPairs.size()); i++) {
            result.add(Arrays.asList(allPairs.get(i)[0], allPairs.get(i)[1]));
        }
        
        return result;
    }
}

复杂度分析

• 时间复杂度：O(mn log mn)。枚举 O(mn)，排序 O(mn log mn)。
• 空间复杂度：O(mn)。

---

三、解法二：最大堆维护K对

思路分析

用最大堆维护当前找到的和最小的 K 对。遍历所有对，如果当前对的和比堆顶小，就替换堆顶。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        // 最大堆，按和排序，保留和最小的k对
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> (b[0] + b[1]) - (a[0] + a[1])
        );
        
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sum = nums1[i] + nums2[j];
                if (maxHeap.size() < k) {
                    maxHeap.offer(new int[]{nums1[i], nums2[j]});
                } else if (sum < maxHeap.peek()[0] + maxHeap.peek()[1]) {
                    maxHeap.poll();
                    maxHeap.offer(new int[]{nums1[i], nums2[j]});
                } else if (sum >= maxHeap.peek()[0] + maxHeap.peek()[1] && j > 0) {
                    // nums2 已排序，后续和更大，可以提前终止内层循环
                    break;
                }
            }
        }
        
        List<List<Integer>> result = new ArrayList<>();
        while (!maxHeap.isEmpty()) {
            int[] pair = maxHeap.poll();
            result.add(Arrays.asList(pair[0], pair[1]));
        }
        
        return result;
    }
}

复杂度分析

• 时间复杂度：O(mn log k)。最坏情况遍历所有对，每次堆操作 O(log k)。
• 空间复杂度：O(k)。

---

四、解法三（最优）：最小堆多路归并

核心思想

把 nums1 的每个元素 nums1[i] 看作一条「虚拟链表」的起点：

• (nums1[0], nums2[0]) → (nums1[0], nums2[1]) → ...
• (nums1[1], nums2[0]) → (nums1[1], nums2[1]) → ...
• ...

每条链表按和递增。初始把每条链表的第一个元素（即 (nums1[i], nums2[0]) for all i）放入最小堆，然后每次取出最小对，并把该链表的下一个元素入堆。

完整代码

import java.util.*;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        List<List<Integer>> result = new ArrayList<>();
        
        if (m == 0 || n == 0 || k == 0) return result;
        
        // 最小堆，元素是 [nums1下标, nums2下标]，按和排序
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]])
        );
        
        // 初始化：nums1 的前 min(m,k) 个元素各与 nums2[0] 配对
        for (int i = 0; i < Math.min(m, k); i++) {
            minHeap.offer(new int[]{i, 0});
        }
        
        while (!minHeap.isEmpty() && result.size() < k) {
            int[] cur = minHeap.poll();
            int i = cur[0], j = cur[1];
            
            result.add(Arrays.asList(nums1[i], nums2[j]));
            
            // 沿 nums2 方向延伸
            if (j + 1 < n) {
                minHeap.offer(new int[]{i, j + 1});
            }
        }
        
        return result;
    }
}

复杂度分析

• 时间复杂度：O(k log min(m,k))。最多取 k 次，每次堆操作 O(log min(m,k))。
• 空间复杂度：O(min(m,k))。堆的大小。

---

五、举一반三

多路归并 + 优先队列的模式：

题目	虚拟「链表」的含义
23. 合并K个链表	每条实际链表
373. K对数字最小和	nums1[i] × nums2 的配对序列
378. 有序矩阵第K小	矩阵每行/每列
786. 第K个最小的素数分数	分子/分母的组合序列

---

六、踩坑实录

坑一：初始只需 min(m,k) 条链表

nums1 可能有 10^5 个元素，但我们只需要前 K 对，所以初始化时只放入 min(m,k) 条虚拟链表（因为后面的链表第一个元素和都比前面大，不可能出现在前K对里）。

如果放入所有 m 条，堆初始大小是 m，O(m log m) 初始化，性能退化。

坑二：比较器用了值而非下标，Comparator 捕获了外部数组

PriorityQueue<int[]> minHeap = new PriorityQueue<>(
    (a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]])
);

这里 Comparator 是个 lambda，引用了外部的 nums1 和 nums2。这在 Java 中是允许的（effectively final），但需要确保在 PriorityQueue 的整个生命周期内 nums1、nums2 不被修改。本题是只读的，没有问题。

坑三：result.size() < k 的终止条件不能省

while (!minHeap.isEmpty()) 加上堆初始化只有 min(m,k) 条链表，理论上最多弹出 k×n 次，但 n 可能很大，必须加 result.size() < k 限制取k对后停止。

---

七、总结

373 是多路归并的标准范例，比 23 更需要「构造虚拟有序序列」的抽象能力。

核心思路：把问题转化为「从多条有序序列中按序取前K个」，然后套多路归并的优先队列框架。初始时每条序列的第一个元素入堆，每次取出最小的并把其后续元素入堆。