Hey there! 我来帮你拆解这道题的最优解法核心逻辑——毕竟暴力法虽然直观，但面对大数组时肯定会超时，这道题的最优思路是二分查找+滑动窗口的组合，我一步步给你讲明白：

先明确问题本质 #

给定整数数组，我们要找所有数对(A,B)中第K小的|A-B|。暴力法是枚举所有数对计算距离，排序后取第K个，时间复杂度O(n²)，但数组长度超过1000的话基本就会超时了。

最优解法的核心思路拆解 #

最优解法的时间复杂度是O(n log n + n log D)（D是数组最大元素和最小元素的差），核心分三步：

1. 先给数组排序

这是整个方法的基础！排序后，数对的距离会呈现出有序的规律，而且我们可以用滑动窗口快速统计"距离≤某个值d的数对总数"。

2. 二分查找目标距离d

我们的目标是找到最小的d，使得数组中距离≤d的数对数量≥K。为什么是这个条件？

• 因为所有可能的距离是从0到max(nums)-min(nums)的连续区间，满足"数对数量≥K"的d一定是一个连续的区间，而我们要找的第K小距离就是这个区间的左边界（最小的那个d）。

举个例子：如果K=3，当d=2时，有5个数对的距离≤2；d=1时，只有2个数对≤1。那第3小的距离肯定是2，因为d=2是第一个满足数对数量≥3的最小值。

3. 滑动窗口统计数对数量

每次二分取到中间值mid后，我们需要快速算出数组中距离≤mid的数对有多少个：

• 用两个指针left和right，初始都在0位置。
• 遍历right从0到n-1：
  • 移动left，直到nums[right] - nums[left] > mid（因为数组排序了，所以nums[right] >= nums[left]，不用绝对值）。
  • 此时，从left到right-1的所有元素和nums[right]组成的数对，距离都≤mid，数量是right - left。
• 把所有right对应的数量累加，就是总共有多少数对的距离≤mid。

举个实际例子帮你理解 #

比如数组[1,3,1]，排序后是[1,1,3]，K=2：

• 二分的初始范围是low=0，high=3-1=2。
• 第一次取mid=1：
  • right=0：left=0，数量0。
  • right=1：nums[1]-nums[0]=0 ≤1，数量1-0=1。
  • right=2：移动left直到nums[2]-nums[left]>1，nums[2]-nums[0]=2>1，nums[2]-nums[1]=2>1，所以left=2，数量0。
  • 总数量是1，小于K=2，所以需要增大d，把low=mid+1=2。
• 第二次mid=(2+2)/2=2：
  • 统计距离≤2的数对：right=0数量0；right=1数量1；right=2时，nums[2]-nums[0]=2≤2，所以left=0，数量2-0=2。总数量1+2=3≥2。
  • 尝试缩小d，把high=mid=2。
• 此时low=high=2，循环结束，d=2就是第2小的距离（数对是(1,3)和(1,3)，距离都是2，加上之前的(1,1)，第2小就是2）。

关键疑问点解答 #

你可能会困惑：为什么找"最小的d满足数对数量≥K"就是第K小的距离？

• 因为距离是从小到大排列的，第K小的距离d_k，所有距离≤d_k的数对数量一定≥K（包含前K个小的距离），而所有距离<d_k的数对数量一定<K（不够K个）。所以这个d_k就是我们要找的最小的满足条件的d。

内容的提问来源于stack exchange，提问作者OLIVER.KOO