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个结果或堆为空时停止

复杂度分析

测试用例

常规测试

输入：

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 List

class 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 result

if __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]]