思路1

超时法：通过两个循环记录三元组[num1,num2,num1+num2]然后通过num1+num2从小到大进行排序，然后返回前K个对数中的前两个数即可。

class Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:if not nums1 or not nums2:return []res=[]for a in nums1:for b in nums2:res.append([a,b,a+b])res.sort(key=lambda x:(x[2]))tmp=[]for i in range(k):tmp.append([res[i][0],res[i][1]])return tmp

思路2

利用最小堆的方法，将 nums1 中前 k 个元素与 nums2[0] 组成的配对 (nums1[i] + nums2[0], i, 0) 压入堆中，表示从 nums2 的第一个元素开始匹配。然后每次从堆中取出当前和最小的数对 (i, j)，加入结果中，并将对应 nums2[j+1] 的新配对 (nums1[i], nums2[j+1]) 加入堆中，逐步扩展。该方法充分利用了两个数组的有序性和堆结构，避免了暴力生成所有配对再排序，时间效率更高。

class Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:if not nums1 or not nums2 or k==0:return []min_heap=[]res=[]for i in range(min(k,len(nums1))):#在nums1中选择最小的k个和nums2匹配heapq.heappush(min_heap,(nums1[i]+nums2[0],i,0))while min_heap and len(res)<k:s,i,j=heapq.heappop(min_heap)res.append([nums1[i],nums2[j]])#nums2中继续找if j+1<len(nums2):heapq.heappush(min_heap,(nums1[i]+nums2[j+1],i,j+1))return res