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：