题目重点：每对由一个a位置与一个b位置组成，重复值位置仍分别计。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 数组可能未排序，示例先复制排序；按和从小到大返回至多K对，K≥0。
- 并列用排序后的(i,j)次序；只返回值，不保留原位置。如需身份排序时附原下标。
解题路线
- 固定a[i]后，a[i]+b[j]随j递增，形成一条有序行。堆只放每活跃行当前最小未读数对。
- 只启用前min(len(a),K)行：更晚行首之前至少已有K个不更大的行首，足够产生一个合法最小K结果；稳定并列合同仍需一致。
- 每弹出(i,j)，只补(i,j+1)。这是K路归并，不必枚举全部mn数对。
手动走一遍
a=[1,7,11],b=[2,4,6],K=3依次(1,2),(1,4),(1,6)，和3/5/7。a=[1,1],b=[2],K=3只存在两个位置对，返回两个(1,2)。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappush, heappop
def smallest_pairs(a, b, k):
if k < 0:
raise ValueError("nonnegative k required")
a, b = sorted(a), sorted(b)
if not a or not b:
return []
heap = [(a[i] + b[0], i, 0) for i in range(min(len(a), k))]
# The list is already heap-ordered because a is sorted.
result = []
while heap and len(result) < k:
_, i, j = heappop(heap)
result.append((a[i], b[j]))
if j + 1 < len(b):
heappush(heap, (a[i] + b[j+1], i, j+1))
return result
复杂度
排序O(m logm+n logn)，堆部分O(min(K,mn)logmin(m,K))，空间O(m+n+K)含排序副本与输出；K=0无堆。
易错点与追问
容易失分的边界
- 用set去重值对会改变按位置组合的合同。
- 只将(a0,b0)入堆再同时扩两方向需visited，否则会重复加入同一对。
继续深挖
- 输入已排序的生成器时，哪些边界读取限制影响堆初始化？
- 返回全部第K小和的并列数对，输出规模会怎样增长？
