https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/
373. Find K Pairs with Smallest Sums
给你两个有序阵列 nums1 和 nums2，任意 nums1 的元素和 nums2 的元素组合 (u, v) 为
一个 Pairs ，求出所有组合中总和最小的 k 个 Pairs。
Example 1:
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
思路：
1.最简单的方式就是用双层循环把所有的组合放进一个Heap里面并依照总和排序，但是
这样时间复杂度是O(n^2*nlogn)，n > 100000 很明显时间会爆掉。
2.我们可以一个一个的把Pair放入Heap，不必把 n^2 种结果都放进去，对于当前最小
Pair {nums[i], nums[j]} 来说，下一个最小的 Pair 必定只能是
{nums1[i], nums2[j + 1]} 或 {nums1[i + 1], nums2[j]} 两者其一，前者对应了
拿下个右边的元素，后者对应了拿下个左边元素，我们可以先把左边的所有元素与右
边最小元素加入Heap，对应了所有的 {nums1[i + 1], nums2[j}，这样每次我们都只要
放入 {nums1[i], nums2[j + 1]}，Heap每次取出来的值都会是最小。
3.另外为了避免 nums1 配对到重复的 nums2，我们还要额外用一个索引纪录当前nums1[i]
已经匹配到右边的哪些索引。
4.这样时间复杂度就压到O(Min(k, n1) * nlogn)，安全范围 = =。
JavaCode：