LeetCode 373 查找和最小的 K 对数字题解

LeetCode 373 查找和最小的 K 对数字题解

题目描述

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

解题思路

最小堆优化法

1. 初始候选集：将nums1每个元素与nums2第一个元素组合
2. 堆维护：使用最小堆动态维护候选对
3. 结果收集：每次取出堆顶元素后补充新的候选对

核心逻辑

1. 堆元素结构：(sum, i, j) 存储当前和、nums1索引、nums2索引
2. 避免重复：通过索引递增保证每个组合只处理一次
3. 提前终止：当收集够k个结果或堆为空时停止

复杂度分析

操作	时间复杂度	空间复杂度
堆初始化	O(klogk)	O(k)
堆弹出/压入	O(klogk)	O(k)
总复杂度	O(klogk)	O(k)

测试用例

常规测试

输入：

nums1 = [1,7,11]
nums2 = [2,4,6] 
k = 3```python
# LeetCode 373 查找和最小的 K 对数字
# https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/import heapq
from typing import Listclass Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:"""解法：最小堆 + 双指针时间复杂度：O(klogk)空间复杂度：O(k)"""if not nums1 or not nums2:return []heap = []# 初始化堆：将nums1中每个元素与nums2第一个元素组合for i in range(min(len(nums1), k)):heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))result = []while heap and len(result) < k:# 取出当前最小和的组合val, i, j = heapq.heappop(heap)result.append([nums1[i], nums2[j]])# 将nums2的下一个元素加入堆（如果存在）if j + 1 < len(nums2):heapq.heappush(heap, (nums1[i] + nums2[j+1], i, j+1))return resultif __name__ == "__main__":# 测试用例test1 = Solution().kSmallestPairs([1,7,11], [2,4,6], 3)  # [[1,2],[1,4],[1,6]]test2 = Solution().kSmallestPairs([1,1,2], [1,2,3], 2)   # [[1,1],[1,1]]