如何用堆找和最小的 K 对数字？

简化版

给两个升序数组找和最小的 K 对，可以把每个 nums1[i] 搭配 nums2[0] 看成一条有序链，先把前若干条链的头放入小顶堆。每次弹出当前最小 pair (i,j)，再把同一条链的下一个 (i,j+1) 入堆。

详细版

如果 nums1 和 nums2 都升序，那么对固定的 i，序列：

(nums1[i], nums2[0]), (nums1[i], nums2[1]), (nums1[i], nums2[2]) ...

按 pair sum 升序排列。于是问题可以看成多路归并：每个 i 是一路，每一路内部有序，用小顶堆每次取当前最小 pair。

步骤：

初始化：把 (i,0) 放入堆，i 从 0 到 min(nums1.length, k)-1。
堆按 nums1[i] + nums2[j] 升序。
每次弹出 (i,j)，加入答案。
如果 j+1 < nums2.length，把 (i,j+1) 入堆。
重复直到取满 K 个或堆空。

时间 O(K log min(n,K))，空间 O(min(n,K))，其中 n 是 nums1 长度。

完整版教学

一、为什么不能暴力枚举所有 pair

两个数组长度分别为 n 和 m，所有 pair 有 n*m 个。如果 n=m=100000，pair 数量达到 10^10，不可能全部生成再排序。题目只要最小的 K 对，K 往往远小于 n*m，所以必须只探索有希望成为答案的前沿。

暴力：
  生成 n*m 个 pair
  排序 O(n*m log(n*m))

堆：
  只维护每一路当前候选
  取 K 次，每次 log(min(n,K))

这类题的关键不是“会用堆”，而是看出升序数组隐含了很多有序链。把二维 pair 空间拆成多条有序链后，就回到了 K 路归并。

二、把二维矩阵看成多条有序链

假设 nums1=[1,7,11]，nums2=[2,4,6]。每个格子 (i,j) 的值是两数之和。因为 nums2 升序，所以每一行从左到右递增。

          nums2
          2   4   6
nums1 1   3   5   7
      7   9  11  13
     11  13  15  17

每一行就是一条有序链：3 -> 5 -> 7、9 -> 11 -> 13、13 -> 15 -> 17。小顶堆先放每行第一个元素，每次弹出最小格子后，只推进它所在行的下一格。

三、为什么初始化只放 min(n,K) 行

如果只需要 K 个答案，最多只可能从前 K 行各取至少一个元素。对于第 K+1 行的第一个 pair，它已经不会早于前 K 行所有头部候选中的至少 K 个潜在答案。把所有 n 行都入堆在 n 很大时会浪费。

K=3
只需要初始化 i=0,1,2 三行：
(0,0), (1,0), (2,0)

第 4 行的 (3,0) 即使很小，也不可能在不比较前三行候选的情况下直接越过全部 K 个名额。

严格实现中常写 for (int i = 0; i < Math.min(nums1.length, k); i++)。这既控制堆大小，也避免 K 很小时的无意义初始化。

四、代码里的状态应该存什么

堆里不应该只存 pair sum，因为弹出后要知道它来自哪一行、哪一列，才能推进到 (i,j+1)。因此堆元素至少要存 (i,j)，sum 可以临时计算，也可以一起存以减少重复计算。

List<List<Integer>> kSmallestPairs(int[] a, int[] b, int k) {
    List<List<Integer>> ans = new ArrayList<>();
    if (a.length == 0 || b.length == 0 || k == 0) return ans;

    PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) ->
        Integer.compare(a[x[0]] + b[x[1]], a[y[0]] + b[y[1]])
    );
    for (int i = 0; i < Math.min(a.length, k); i++) pq.offer(new int[]{i, 0});

    while (k-- > 0 && !pq.isEmpty()) {
        int[] cur = pq.poll();
        int i = cur[0], j = cur[1];
        ans.add(Arrays.asList(a[i], b[j]));
        if (j + 1 < b.length) pq.offer(new int[]{i, j + 1});
    }
    return ans;
}

如果数值范围大，比较 sum 时也要用 long，避免 a[i] + b[j] 溢出。状态设计和溢出处理是这题常见扣分点。

五、和“合并 K 个有序链表”的关系

这题可以看成合并 K 条有序链表，只不过链表节点不是显式存在的，而是由数组下标 (i,j) 隐式生成。弹出一个节点后，下一节点就是 (i,j+1)。这种“隐式图/隐式链”是堆题很重要的抽象能力。

题型	一路是什么	堆里存什么	弹出后补什么
合并 K 个链表	一条链表	节点指针	node.next
合并 K 个数组	一个数组	数组编号和下标	同数组下一个
K 对最小和	固定 i 的一行 pair	`(i,j)`	`(i,j+1)`

看到“有序矩阵取前 K 小”“两个有序数组组合取前 K 小”，都可以先问自己：能否拆成多条有序链，然后用小顶堆归并。

六、常见误区与追问

记忆钩子：这题不是枚举 pair，而是在二维有序矩阵里沿着每一行的前沿推进。

误区：必须生成所有 n*m 个 pair 再排序。 K 通常很小，全部生成会超时或爆内存。
误区：堆里只存 pair 的和就够了。 弹出后不知道从哪里推进下一候选，必须存下标。
误区：初始化要把所有行都放入堆。 只取 K 个答案时，初始化 min(n,K) 行即可。
追问：为什么弹出后只推进 j+1？ 固定 i 的这一行按 nums2 升序，下一候选就是右边一格。
追问：如果数组有负数还成立吗？ 只要两个数组各自升序，每一行仍然按 nums2 递增，方法成立。
追问：比较器有什么风险？ 两数之和可能溢出，范围大时用 long 比较。

七、加强记忆

K 对最小和的本质是“隐式 K 路归并”。把固定 nums1[i] 的所有 pair 看成一条按和递增的链，先把每条链的头放入小顶堆；每弹出一个 pair，就把同一条链的下一个 pair 补进去。这样只探索答案边界附近的 K 次前沿，而不是铺开 n*m 个组合。记住“二维矩阵、行内有序、堆存坐标、弹出后右移”，这类题就不会被组合数量吓住。

简化版

详细版