题目:
题解:
func kSmallestPairs(nums1, nums2 []int, k int) (ans [][]int) {m, n := len(nums1), len(nums2)// 二分查找第 k 小的数对和left, right := nums1[0]+nums2[0], nums1[m-1]+nums2[n-1]+1pairSum := left + sort.Search(right-left, func(sum int) bool {sum += leftcnt := 0i, j := 0, n-1for i < m && j >= 0 {if nums1[i]+nums2[j] > sum {j--} else {cnt += j + 1i++}}return cnt >= k})// 找数对和小于 pairSum 的数对i := n - 1for _, num1 := range nums1 {for i >= 0 && num1+nums2[i] >= pairSum {i--}for _, num2 := range nums2[:i+1] {ans = append(ans, []int{num1, num2})if len(ans) == k {return}}}// 找数对和等于 pairSum 的数对i = n - 1for _, num1 := range nums1 {for i >= 0 && num1+nums2[i] > pairSum {i--}for j := i; j >= 0 && num1+nums2[j] == pairSum; j-- {ans = append(ans, []int{num1, nums2[j]})if len(ans) == k {return}}}return
}