主題
題目連結：
題目意譯：
一對整數 a 和 b 的「距離」定義為 a 和 b 的絕對差值。
給定一個整數陣列 nums 以及一個整數 k。回傳在所有可能的 nums[i] 和 nums[j] 所形成的整數對中第 k 小之距離值，其中 0 ≦ i < j < nums.length。
限制：
n == nums.length
2 ≦ n ≦ 10 ^ 4
0 ≦ nums[i] ≦ 10 ^ 6
1 ≦ k ≦ n × (n - 1) / 2
範例測資：
範例 1：
輸入： nums = [1,3,1], k = 1
輸出： 0
解釋： 以下是所有可能的整數對：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距離最 1 小整數對為 (1,1)，而其距離值為 0。
範例 2：
輸入： nums = [1,1,1], k = 2
輸出： 0
範例 3：
輸入： nums = [1,6,1], k = 3
輸出： 5
解題思維：
跟這題類似，也是一題可以對「答案」進行二分搜尋法（Binary Search）的題型。
假設現在猜了第 k 小的距離值為 D，那要怎麼檢查有沒有猜得太大呢？
首先，將 nums 中的數字由小排到大。接著對 nums[0] 找到一個索引值 x 使得 0 < x ≦ nums.length 、 nums[x] - nums[0] > D 且 nums[x - 1] - nums[0] ≦ D，其中 x == nums.length 若且唯若 nums[0] + D 都不小於 nums[0] 後面的數字。
可以看到包含 nums[0] 且符合條件的整數對之數量即為 x - 0 個。
而我們可以對任意索引值 i，做類似的事情並定義出類似的 x 值。但是我們可以看到，對於相鄰索引值 nums[i] 和 nums[i + 1] 而言，兩者的 x 值（前者稱為 a；後者為 b）會滿足 a ≦ b。因此從 nums[i] 移動到 nums[i + 1] 時不需要從 i + 1 開始重新判斷，可以直接繼承 a 之值繼續往後延伸到目標 b 即可。
因此我們可以看到從 i = 0 開始往後推算，過程中的 x 值也只會跟著往右不會回頭。因此單次檢查的時間複雜度為 O(nums.length)，不計入一開始排序的時間。
而各個包含 nums[i] 且符合條件的整數對之數量即為 x - i 個。
將這些「x - i」值加總並判斷有沒有小於等於 k。根據有沒有小於等於 k 便可以知道原本猜的距離值 D 有沒有太大。太大大小都可以進行調整。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
