Python | Leetcode Python题解之第373题查找和最小的K对数字

题目：

题解：

class Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:m, n = len(nums1), len(nums2)# 二分查找第 k 小的数对和left, right = nums1[0] + nums2[0], nums1[m - 1] + nums2[n - 1] + 1while left < right:mid = (left + right) // 2cnt = 0i, j = 0, n - 1while i < m and j >= 0:if nums1[i] + nums2[j] > mid:j -= 1else:cnt += j + 1i += 1if cnt < k:left = mid + 1else:right = midpairSum = leftans = []# 找数对和小于 pairSum 的数对i = n - 1for num1 in nums1:while i >= 0 and num1 + nums2[i] >= pairSum:i -= 1for j in range(i + 1):ans.append([num1, nums2[j]])if len(ans) == k:return ans# 找数对和等于 pairSum 的数对i = n - 1for num1 in nums1:while i >= 0 and num1 + nums2[i] > pairSum:i -= 1j = iwhile j >= 0 and num1 + nums2[j] == pairSum:ans.append([num1, nums2[j]])if len(ans) == k:return ansj -= 1return ans