LeetCode 373中等堆
查找和最小的 K 对数字 图解题解
这道题到底在问什么
给两个升序数组 nums1、nums2 和整数 k，从 nums1×nums2 的所有 (a,b) 对中，返回和最小的 k 对。
- 输入
- nums1=[1,7,11], nums2=[2,4,6], k=3
- 输出
- [[1,2],[1,4],[1,6]]
最优解：一步一步想明白
- 3记住这条「行首入堆·弹最小·只补右邻一对」，下面每一步都在套它。
- 4开始：堆是空的（容量 3）。先把 nums1 每个数配 nums2[0]=2 的对依次入堆——它们是每一行里和最小的候选。
- 5把 (1,2) 入堆： 先放到堆末尾(下标0)，再按对和向上浮到该去的位置。
- 6把 (7,2) 入堆： 先放到堆末尾(下标1)，再按对和向上浮到该去的位置。
- 7新对 (7,2)和9 ≥ 父 (1,2)和3，停止上浮、就位(绿)。堆顶 (1,2)仍是当前最小和。
- 8把 (11,2) 入堆： 先放到堆末尾(下标2)，再按对和向上浮到该去的位置。
- 9新对 (11,2)和13 ≥ 父 (1,2)和3，停止上浮、就位(绿)。堆顶 (1,2)仍是当前最小和。
- 10堆顶 (1,2) 和=3，是当前所有候选里对和最小的，弹出收进答案。
- 11(1,2) 收进答案(第1对)。把堆末元素 (11,2) 暂放堆顶(紫)，再按对和向下沉。
- 12比较 (11,2)和13 与较小子 (7,2)和9：子更小，下沉交换。
- 13交换完成，(11,2)沉到下标1。
- 14(11,2) 对和已不大于子节点，下沉结束(绿就位)，堆顶 (7,2)又是当前最小和。
- 15刚弹的对来自 nums1[0]=1 这行，补它右邻 (1,4) 入堆： 先放到堆末尾(下标2)，再按对和向上浮到该去的位置。
- 16比较新对 (1,4)和5 与父 (7,2)和9：更小，上浮交换。
- 17交换完成，新对上浮到下标0。
- 18新对 (1,4)和5 已浮到堆顶，就是当前最小和，就位(绿)。
- 19堆顶 (1,4) 和=5，是当前所有候选里对和最小的，弹出收进答案。
- 20(1,4) 收进答案(第2对)。把堆末元素 (7,2) 暂放堆顶(紫)，再按对和向下沉。
- 21(7,2) 对和已不大于子节点，下沉结束(绿就位)，堆顶 (7,2)又是当前最小和。
- 22刚弹的对来自 nums1[0]=1 这行，补它右邻 (1,6) 入堆： 先放到堆末尾(下标2)，再按对和向上浮到该去的位置。
- 23比较新对 (1,6)和7 与父 (7,2)和9：更小，上浮交换。
- 24交换完成，新对上浮到下标0。
- 25新对 (1,6)和7 已浮到堆顶，就是当前最小和，就位(绿)。
- 26堆顶 (1,6) 和=7，是当前所有候选里对和最小的，弹出收进答案。
- 27(1,6) 收进答案(第3对)。把堆末元素 (7,2) 暂放堆顶(紫)，再按对和向下沉。
- 28(7,2) 对和已不大于子节点，下沉结束(绿就位)，堆顶 (7,2)又是当前最小和。
- 29已弹满 3 对，按和从小到大依次是 (1,2)、(1,4)、(1,6)，正是答案。
⚠️ 容易写错的地方
✗ 错：把 nums1×nums2 全部对一次性入堆
✓ 对：只入每行行首 (i,0)，弹一个再补右邻
全入堆退化成 O(mn log(mn))，k 很小时白白多算
✗ 错：弹出后把整行剩余都补进堆
✓ 对：只补紧邻的 (i,j+1) 一个
同一行更靠后的对一定更大，提前补进去只是占位浪费
✗ 错：Java 比较器用 a[0]-b[0] 在极端值溢出
✓ 对：值可能极大时用 Integer.compare(a[0],b[0])
两个 int 相减可能溢出，导致堆序错乱
完整代码（Python / C++ / Java）
Python
import heapq
def kSmallestPairs(nums1, nums2, k):
if not nums1 or not nums2: return []
h = [] # 最小堆: (对和, i, j)
for i in range(min(k, len(nums1))):
heapq.heappush(h, (nums1[i]+nums2[0], i, 0))
res = []
while h and len(res) < k:
_, i, j = heapq.heappop(h) # 弹最小对
res.append([nums1[i], nums2[j]])
if j + 1 < len(nums2): # 只补右邻一对
heapq.heappush(h, (nums1[i]+nums2[j+1], i, j+1))
return resC++
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k){
using T = tuple<int,int,int>; // (对和, i, j)
priority_queue<T, vector<T>, greater<T>> h;
int m = nums1.size(), n = nums2.size();
if(!m || !n) return {};
for(int i = 0; i < min(k, m); i++) h.push({nums1[i]+nums2[0], i, 0});
vector<vector<int>> res;
while(!h.empty() && (int)res.size() < k){
auto [s, i, j] = h.top(); h.pop(); // 弹最小对
res.push_back({nums1[i], nums2[j]});
if(j + 1 < n) h.push({nums1[i]+nums2[j+1], i, j+1}); // 补右邻
}
return res;
}Java
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k){
List<List<Integer>> res = new ArrayList<>();
if(nums1.length == 0 || nums2.length == 0) return res;
// 最小堆，元素 [对和, i, j]，按对和升序
PriorityQueue<int[]> h = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for(int i = 0; i < Math.min(k, nums1.length); i++)
h.offer(new int[]{nums1[i] + nums2[0], i, 0});
while(!h.isEmpty() && res.size() < k){
int[] cur = h.poll(); // 弹最小对
int i = cur[1], j = cur[2];
res.add(Arrays.asList(nums1[i], nums2[j]));
if(j + 1 < nums2.length) // 只补右邻一对
h.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
}
return res;
}复杂度
时间
O(k log k)
初始入堆 min(k,m) 个，之后每弹一对补一对、各 O(log k)，共弹 k 次
空间
O(min(k, m))
堆里最多 min(k, m) 个候选（每行至多一个）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 查找和最小的 K 对数字 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
初始为什么入堆只放 min(k, m) 个，而不是全部 m 个行首？+
最终只取 k 对，行首和已升序，超过 k 行的行首一定排在更后、不可能进前 k，放进去也是浪费，所以只入前 min(k, m) 个。
为什么堆元素要带上 i、j 下标？+
弹出后要知道「这对来自哪一行的第几列」才能补它的右邻 (i, j+1)；同时和相等时带下标可让元组比较有确定次序、避免比较对象本身。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 查找和最小的 K 对数字 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。