数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
有点脑筋急转弯。
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
# 本题有脑筋急转弯的性质
_len = len(nums)
# 给定距离dist，计算小于等于mid的个数
# 注意，随着dist的增加，个数一定不会减少
def count(mid):
# 双指针法
# 从0开始寻找差距小于mid的有几个
r = 1
cnt = 0
for l in range(_len):
while r < _len and nums[r] - nums[l] <= mid:
r += 1
# print('l,r :', l, r)
cnt += r - 1 - l
return cnt
nums.sort()
# bisect(arr, x, key) python 3.10中的函数
# arr 数组
# x值
# key计算比较函数
# 计算x在比较函数中的位置
# x代表数对差的绝对值
# 比x小于等于的数对有key(x)个，那么令k=key(x)，搜索求出x1，x2,x3等等，其中返回x1（保证是等于）
# 即小于等于x1的数对有k个，且x1为存在的数对差的绝对值
return bisect_left(range(nums[-1] - nums[0]), k, key=count)
