这道题我刷过好几遍每次遇到都有朋友在评论区问为什么排序之后要用二分双指针计数为什么总是差一个数甚至有人直接暴力算所有数对然后排序取第 k 个提交直接超时。今天就把“找出第 K 小的数对距离”这道题从头到尾拆干净把思路、代码、边界、坑全部捋清楚适合正在刷题准备面试的朋友也适合想补一补二分和双指针基础的人。标题里那几个关键词——排序、二分答案、双指针计数其实是一个完整的套路组合理解之后很多“第 k 小/大”的题都能套用。1. 先把这个题真正读懂案例入手1.1 题面与最直观的暴力做法题目说的是给定一个整数数组 nums 和一个整数 k要返回所有数对距离中第 k 小的那个。数对距离就是两个数的绝对差比如数组 [1, 3, 1]所有数对距离是 |1-3|2、|1-1|0、|3-1|2排序后是 [0, 2, 2]第 1 小是 0第 2 小是 2第 3 小还是 2。注意 k 从 1 开始计数不是从 0 开始。最直接的做法就是把所有数对距离都求出来放进一个数组排序之后按下标取。这段代码写起来很舒服两层 for 循环算绝对差push 到数组里最后排个序。数据规模小的时候完全没问题比如 n 100数对数量 4950随便算。但题目通常给的是 n 最大可以到 10^4 或者 10^5这时候数对数量是 n(n-1)/2也就是千万级别甚至亿级别。把所有距离存下来排序时间和空间都扛不住。某场笔试我试过n 10^4 的数据量暴力做直接运行超时内存也差点爆掉。所以这道题真正的考点不是“会不会求距离”而是“能不能在不大规模枚举的情况下找到答案”。1.2 为什么暴力过不了复杂度账要算清算一笔账就清楚了。n 10^4数对数量大约是 5×10^7也就是五千万。生成这些数对是 O(n^2) 的循环排序五千万个数需要 O(n log n)无论时间还是内存都很难接受。更别提 n 10^5 时数对数量直接到 5×10^9暴力连跑都跑不完。这时候要换思路既然直接枚举所有数对不现实能不能不枚举所有数对而是“猜”一个答案然后验证这个答案是不是第 k 小这就是二分答案的由来。二分答案配合双指针计数能把复杂度降到 O(n log n n log M)其中 M 是距离的最大值也就是数组最大值减最小值。这个复杂度在面对 n 10^5、M 10^6 的时候是轻轻松松的。很多人第一次听到“二分答案”会觉得奇怪答案又不是在数组里取值怎么二分实际上二分的对象是“距离”这个数值范围而不是数组下标。距离一定在 0 到 max(nums) - min(nums) 之间我们在这个区间里猜一个值 mid然后数一数“有多少个数对的距离小于等于 mid”。如果这个数量大于等于 k说明第 k 小的距离不超过 mid答案应该在左侧如果数量小于 k说明第 k 小的距离比 mid 大答案在右侧。这个过程本质上是在一个单调的序列上做二分单调性来自“小于等于某个值的数对数量”随着 mid 增大只增不减。2. 核心思路把“第 k 小”转成“小于等于某个值的数量”2.1 单调性是二分答案的前提这里最关键的一步是理解 count(mid) 这个函数。定义 count(mid) 距离小于等于 mid 的数对个数。当 mid 从 0 慢慢增加到最大距离时符合条件的数对只会越来越多绝对不会减少。就好比一个门槛不断抬高能跨过门槛的人只会更多。这个单调性是二分答案能成立的根基。有了单调性就能做区间收缩。假设当前距离区间是 [left, right]取中点 mid。如果 count(mid) k说明距离 mid 已经足够容纳 k 个数对了真正的第 k 小距离不会大于 mid所以把 right 收缩到 mid。如果 count(mid) k说明连 mid 这么宽松的条件都凑不够 k 个数对那答案一定大于 mid把 left 收缩到 mid 1。反复缩小直到 left 和 right 相遇。这里有个容易误解的点为什么 count(mid) k 时答案在左侧而不是左侧或等于 mid因为如果 count(mid) 已经大于等于 kmid 可能刚好就是答案也可能比答案大但答案绝对不可能在 mid 右边。收缩右侧区间不会把正确答案丢掉。反过来count(mid) k 说明 mid 太宽松了都凑不够数答案一定在右侧所以 left 可以直接跳过 mid 到 mid 1。这个逻辑想清楚二分边界就不容易写错。2.2 二分的区间边界到底怎么定二分区间初始化有两个常见的写法一种是 left 0、right max(nums) - min(nums)这是距离的可能范围另一种是 left 0、right 10^9 之类的上限。第一种更精确能减少几次迭代推荐使用。如果数组只有一个元素那距离只有 0right 也是 0不会进入循环直接返回 0这属于边界特判很多实现里不需要额外处理因为二分循环条件 while left right 直接不满足。每次迭代取 mid left (right - left) // 2注意这里用这个写法而不是 (left right) // 2是为了防止 left right 溢出。虽然 Python 不会溢出但如果你写 Java 或者 C还是养成习惯比较好。这个细节在面试里说出口会显得你考虑问题比较全面。还有一点要注意这里的 k 是第 k 小从 1 开始。而 count(mid) 返回的是数量本身从 0 开始数。所以判断条件是 count(mid) k不是 k。我在某次帮朋友排查代码时发现他把条件写成了 count(mid) k导致正确答案总是偏小一位查了半天才发现是边界条件差了一个等号。3. 双指针计数整个题最容易写崩的部分3.1 双指针为什么能算“小于等于 mid 的对数”排序之后数组是升序的这是双指针能用的前提。排序的意义在于对于任意 i jnums[j] - nums[i] 就是这两个数的距离。如果我们固定左端 i然后让右端 j 向右移动直到 nums[j] - nums[i] mid那么从 i1 到 j-1 的所有位置和 i 组成的数对距离都小于等于 mid一共 j - i - 1 个。然后 i 向右移动一格j 不需要回到 i1 重新开始而是继续保持在当前位置或者继续向右。为什么可以这样因为当 i 增大时nums[i] 变大nums[i1] 到 nums[j-1] 与 i1 的距离只会更小j 不会往左退。这就是双指针的滑动窗口本质。我用一个生活化的类比解释想象你在一排递增的数字前面左手固定在一个数上右手往右摸摸到距离超过 mid 就停左手指向的数能和右手之前摸过的所有数组成合法数对。左手往右挪一格右手继续往前摸反正右手指向的数只会越来越大不会回头。整个过程左右手都只往右走每个数字最多被摸两次所以计数是 O(n) 的。这个思路实现起来看起来简单但很多人第一次写会懵主要原因是计数公式到底是 j - i 还是 j - i - 1right 指针初始值应该是 i 还是 i1循环结束条件是 right n 还是 right n这些细节差一点结果就差很多。3.2 三种常见的计数写法与边界分析先放一个通用的逻辑框架def count_pairs(nums, mid): n len(nums) cnt 0 j 0 for i in range(n): while j n and nums[j] - nums[i] mid: j 1 cnt j - i - 1 return cnt这里的 while 循环会把 j 移动到第一个使得 nums[j] - nums[i] mid 的位置也就是 j 指向的是第一个“不合法”的位置。此时从 i1 到 j-1 都合法数量是 j - i - 1。为什么减 1因为 j 比最后一个合法位置多 1减去 i 之后还要把 i 自己排除掉。举个例子nums [1, 2, 3, 4]mid 1。当 i 0nums[i]1j 从 0 开始nums[0] - nums[0] 0 1j 变 1nums[1] - nums[0] 1 1j 变 2nums[2] - nums[0] 2 1循环停止j 2。此时合法位置是 1 和 2 吗不对合法位置是 i11 到 j-11也就是只有下标 1 一个。j - i - 1 2 - 0 - 1 1正确。第二种写法是固定 i让 j 从 i1 开始然后向右移动。代码长这样def count_pairs(nums, mid): n len(nums) cnt 0 j 1 for i in range(n): if j i: j i 1 while j n and nums[j] - nums[i] mid: j 1 cnt j - i - 1 return cnt这种写法多了很多边界处理实际上没必要。第三种写法是让 j 从 0 开始但不使用 j - i - 1而是用另一个变量维护窗口大小有些炫技不推荐。三种写法里第一种最简洁逻辑最容易验证。j 初始化为 0 不会影响正确性因为 while 循环会先把 j 增加到合理位置只有在第一次进入循环时 i0 时 j0 会导致 nums[j]-nums[i]0 计入一个“自身对”但随后 j 会移动到 1实际最终计数时 j - i - 1 把自身排除了。你可以在纸上跑一遍会发现结果完全正确。3.3 边界偏移量j-i-1 还是 j-i为什么会错很多人的 bug 出在 cnt j - i 上。这个错误特别隐蔽因为有些输入数据下结果是错的有些输入下碰巧是对的。问题在于 j 的含义不统一。如果 while 循环结束后 j 指向的是当前 i 的“第一个非法位置”那么 j - i 会把 i 自己和 j 指向的那个非法位置也算进去吗算进去的只有 i 自己非法位置不在窗口里。但 j - i 得到的数量比合法数量多 1因为把 i 自己加进去了。所以必须减 1。还有一种常见的错误是使用 j - i但是 while 循环条件写成 nums[j] - nums[i] mid严格小于这种情况下结果会漏掉距离恰好等于 mid 的数对。注意题目要求“小于等于”用 才是对的。我在实际写代码时会在 while 条件后面写注释“ mid不是 mid”提醒自己。另外判断 count(mid) 时如果 cnt 已经大于等于 k可以提前退出不需要算完整个数组。这是非常有效的剪枝因为二分过程中 mid 可能很大count 很快就能超过 k提前 return 能省掉大量不必要的遍历。4. 完整代码与复杂度说明4.1 Python 实现把上面的思路整合起来完整代码如下def smallest_distance_pair(nums, k): nums.sort() n len(nums) def count_pairs(mid): cnt 0 j 0 for i in range(n): while j n and nums[j] - nums[i] mid: j 1 cnt j - i - 1 if cnt k: return cnt return cnt left, right 0, nums[-1] - nums[0] while left right: mid left (right - left) // 2 if count_pairs(mid) k: right mid else: left mid 1 return left这个实现有几个点需要说明。第一提前剪枝在 count_pairs 里当 cnt k 时直接返回因为只需要知道“够不够”不需要精确值。第二right 的初始化是 nums[-1] - nums[0]在排序后直接取最大距离比设置一个大数更精确。第三while left right 的循环退出时 left 就是答案不需要再做额外的判断。4.2 Java 实现很多面试场景用 Java我也写一版public int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); int n nums.length; int left 0; int right nums[n - 1] - nums[0]; while (left right) { int mid left (right - left) / 2; if (countPairs(nums, mid, k) k) { right mid; } else { left mid 1; } } return left; } private int countPairs(int[] nums, int mid, int k) { int cnt 0; int j 0; int n nums.length; for (int i 0; i n; i) { while (j n nums[j] - nums[i] mid) { j; } cnt j - i - 1; if (cnt k) { return cnt; } } return cnt; }把 k 传入 countPairs 是用于提前退出这样函数语义更清楚。Java 里注意数组排序用的是 Arrays.sort时间复杂度 O(n log n)。int 类型的 cnt 在某些极端数据下可能会超过 2^31-1 吗n 最多 10^5 时cnt 最大是 n(n-1)/2 ≈ 5×10^9确实超过 int 范围所以更稳妥的做法是把 cnt 声明为 long并在 cnt k 时提前返回。如果 n 能到 10^6那 long 也稳。所以 Java 版我习惯把 cnt 写 long避免溢出问题。4.3 复杂度与常数优化排序 O(n log n)。二分循环次数是 O(log M)M 是最大距离。每次二分调用 count_pairs 是 O(n)。总体 O(n log n n log M)。空间复杂度 O(1)只用了几个变量没有额外的大数组。常数优化方面一个是提前退出另一个是局部变量的使用。Python 里 while 循环内部的 nums[j] 和 nums[i] 访问很快不需要额外优化。但要注意每次调用 count_pairs 都重新遍历数组这个遍历本身是 O(n)在整个二分过程中会执行约 log M 次对于 n10^5、M10^9 来说log M 大约 30所以总操作量是 3×10^6 次量级非常快。这里有个细节为什么不是二分“答案”的索引而是二分“数值”因为答案的取值范围是连续的整数从 0 到 max-min直接对数值二分不需要额外的存储。有些类似题目比如“第 k 小的子数组和”也可以套用这个思路但子数组和不能直接对和值二分因为和值可能非常大而距离这个指标天然就是 int 范围内的有限值所以二分非常自然。5. 实战中的坑与排查思路5.1 二分死循环问题二分最怕死循环。left 1、right 2mid 1如果 count(mid) 满足条件让 right mid区间变成 [1, 1]正常退出如果条件不满足让 left mid 1 2区间变成 [2, 2]也正常退出。但如果你把 mid 的计算写成 mid right - (right - left) // 2向上取整并且条件满足时 right mid区间可能会卡住。我调试过一只 bug就是 unknowingly 用了向上取整导致 left 和 right 永远在相邻的两个数之间震荡。规范做法是mid left (right - left) // 2向下取整条件满足时 right mid不满足时 left mid 1。这个组合一定不会死循环。记住这个口诀“向下取整左闭右开收缩”。如果你换成向上取整就必须配套 left mid 和 right mid - 1另一种写法也是对的但新手容易记混不如统一用向下取整。5.2 计数结果溢出与精度问题前面提到 cnt 可能超过 int 上限这是实战中容易忽视的点。Python 的 int 是无限精度问题不大但写 Java 或 C 时建议用 long。除了溢出还有 k 的取值问题。k 最大是 n(n-1)/2所以 k 本身也可能超过 int但题目一般保证 k 是 int 范围内所以你只需要关心 cnt 会不会超过 int。为了保险count_pairs 里 cnt 遇到 k 直接返回这样实际上 cnt 永远不会真正累加到最大值只在 k 很接近 n(n-1)/2 的时候可能累加到接近这个值此时用 long 就没错。这也是一个很自然的优化思路我不需要算出一个精确的 count 再来比较而是边算边比较提前返回。5.3 排序与不排序的区别为什么非排序不可不排序能不能用双指针不能。双指针的核心是窗口内元素有序才能通过单调性推断“右侧只要距离超过 mid右指针就不必回退”。如果不排序nums[j] - nums[i] 不是单调的j 没法不回退计数就退化成 O(n^2)。而排序本身 O(n log n) 的代价是可以接受的因为题目没有要求保持原数组顺序任何修改数组的行为都是允许的。如果你在面试中遇到“能不能不排序”的问题可以这样解释排序是为了给双指针一个单调的环境用 O(n log n) 的预处理换取每次 O(n) 的计数是这道题最优解的必要组成部分。还有一个小细节如果数组中存在负数排序后最大距离仍然是 nums[-1] - nums[0]因为最小数在排序后在最前面最大数在最后面绝对差的最大值一定来自这两个数。这个结论在排序后自然成立不需要额外处理。5.4 几个真实踩坑案例我见过朋友写错的一种情况在 count_pairs 里把 j 放在 for 循环外面但每次重新计算时没有把 j 重置为 0。这会导致第二次调用 count_pairs 时 j 延续上一次的位置计数值完全错乱。正确的做法是每次进入 count_pairs 都把 j 初始化为 0。这个 bug 之所以难发现是因为单次调用时结果是对的但二分需要多次调用第二次就出问题。我建议在 count_pairs 函数内部定义 j不要作为参数传进去这样从结构上杜绝这个错误。还有一种情况是在 while 循环条件里先判断 i 和 j 的大小关系比如写成 while j i and nums[j] - nums[i] mid这会导致自身对永远被排除最终结果比正确答案小。其实 j 从 0 开始在 for i 循环中当 i 增大时 j 可能小于等于 i比如 nums 里有大量重复元素时while 条件 nums[j] - nums[i] mid 可能对 j i 也成立j 会先跳过 i不会出现 j i 的情况。所以不需要额外判断 j 和 i 的关系。想通这一点就明白为什么最简写法足够稳。最后分享一个我自己的习惯写完代码后用一个非常小的例子手动走一遍比如 nums [1, 3, 1], k 1排序后变成 [1, 1, 3]然后手算 count(0) 应该等于 1一对相同元素的距离为 0count(1) 等于 2两个 1 的距离是 01 和 3 的距离是 2 1所以只有 1 对不对距离 0 算一对1 和 3 不算所以 count(1) 还是 1。手算能立刻发现边界问题比直接提交省时间。在实际刷题过程中我体会到这类“第 k 小”问题最核心的套路就是“二分答案 计数验证”。一旦你习惯用 count(mid) 的视角去看问题很多看似复杂的题目都能归约到同一个框架里。如果你正在准备面试建议把这一题的三种边界写法都亲手跑一遍再用 [1, 1, 1] 这种全是重复元素的极端用例测一下确认自己的代码不会在重复元素上出错。这样下次再遇到类似题目你就能直接默写出正确框架而不是每次都得现场从零推理边界。 排序+二分答案+双指针：秒杀第K小的数对距离
这道题我刷过好几遍每次遇到都有朋友在评论区问为什么排序之后要用二分双指针计数为什么总是差一个数甚至有人直接暴力算所有数对然后排序取第 k 个提交直接超时。今天就把“找出第 K 小的数对距离”这道题从头到尾拆干净把思路、代码、边界、坑全部捋清楚适合正在刷题准备面试的朋友也适合想补一补二分和双指针基础的人。标题里那几个关键词——排序、二分答案、双指针计数其实是一个完整的套路组合理解之后很多“第 k 小/大”的题都能套用。1. 先把这个题真正读懂案例入手1.1 题面与最直观的暴力做法题目说的是给定一个整数数组 nums 和一个整数 k要返回所有数对距离中第 k 小的那个。数对距离就是两个数的绝对差比如数组 [1, 3, 1]所有数对距离是 |1-3|2、|1-1|0、|3-1|2排序后是 [0, 2, 2]第 1 小是 0第 2 小是 2第 3 小还是 2。注意 k 从 1 开始计数不是从 0 开始。最直接的做法就是把所有数对距离都求出来放进一个数组排序之后按下标取。这段代码写起来很舒服两层 for 循环算绝对差push 到数组里最后排个序。数据规模小的时候完全没问题比如 n 100数对数量 4950随便算。但题目通常给的是 n 最大可以到 10^4 或者 10^5这时候数对数量是 n(n-1)/2也就是千万级别甚至亿级别。把所有距离存下来排序时间和空间都扛不住。某场笔试我试过n 10^4 的数据量暴力做直接运行超时内存也差点爆掉。所以这道题真正的考点不是“会不会求距离”而是“能不能在不大规模枚举的情况下找到答案”。1.2 为什么暴力过不了复杂度账要算清算一笔账就清楚了。n 10^4数对数量大约是 5×10^7也就是五千万。生成这些数对是 O(n^2) 的循环排序五千万个数需要 O(n log n)无论时间还是内存都很难接受。更别提 n 10^5 时数对数量直接到 5×10^9暴力连跑都跑不完。这时候要换思路既然直接枚举所有数对不现实能不能不枚举所有数对而是“猜”一个答案然后验证这个答案是不是第 k 小这就是二分答案的由来。二分答案配合双指针计数能把复杂度降到 O(n log n n log M)其中 M 是距离的最大值也就是数组最大值减最小值。这个复杂度在面对 n 10^5、M 10^6 的时候是轻轻松松的。很多人第一次听到“二分答案”会觉得奇怪答案又不是在数组里取值怎么二分实际上二分的对象是“距离”这个数值范围而不是数组下标。距离一定在 0 到 max(nums) - min(nums) 之间我们在这个区间里猜一个值 mid然后数一数“有多少个数对的距离小于等于 mid”。如果这个数量大于等于 k说明第 k 小的距离不超过 mid答案应该在左侧如果数量小于 k说明第 k 小的距离比 mid 大答案在右侧。这个过程本质上是在一个单调的序列上做二分单调性来自“小于等于某个值的数对数量”随着 mid 增大只增不减。2. 核心思路把“第 k 小”转成“小于等于某个值的数量”2.1 单调性是二分答案的前提这里最关键的一步是理解 count(mid) 这个函数。定义 count(mid) 距离小于等于 mid 的数对个数。当 mid 从 0 慢慢增加到最大距离时符合条件的数对只会越来越多绝对不会减少。就好比一个门槛不断抬高能跨过门槛的人只会更多。这个单调性是二分答案能成立的根基。有了单调性就能做区间收缩。假设当前距离区间是 [left, right]取中点 mid。如果 count(mid) k说明距离 mid 已经足够容纳 k 个数对了真正的第 k 小距离不会大于 mid所以把 right 收缩到 mid。如果 count(mid) k说明连 mid 这么宽松的条件都凑不够 k 个数对那答案一定大于 mid把 left 收缩到 mid 1。反复缩小直到 left 和 right 相遇。这里有个容易误解的点为什么 count(mid) k 时答案在左侧而不是左侧或等于 mid因为如果 count(mid) 已经大于等于 kmid 可能刚好就是答案也可能比答案大但答案绝对不可能在 mid 右边。收缩右侧区间不会把正确答案丢掉。反过来count(mid) k 说明 mid 太宽松了都凑不够数答案一定在右侧所以 left 可以直接跳过 mid 到 mid 1。这个逻辑想清楚二分边界就不容易写错。2.2 二分的区间边界到底怎么定二分区间初始化有两个常见的写法一种是 left 0、right max(nums) - min(nums)这是距离的可能范围另一种是 left 0、right 10^9 之类的上限。第一种更精确能减少几次迭代推荐使用。如果数组只有一个元素那距离只有 0right 也是 0不会进入循环直接返回 0这属于边界特判很多实现里不需要额外处理因为二分循环条件 while left right 直接不满足。每次迭代取 mid left (right - left) // 2注意这里用这个写法而不是 (left right) // 2是为了防止 left right 溢出。虽然 Python 不会溢出但如果你写 Java 或者 C还是养成习惯比较好。这个细节在面试里说出口会显得你考虑问题比较全面。还有一点要注意这里的 k 是第 k 小从 1 开始。而 count(mid) 返回的是数量本身从 0 开始数。所以判断条件是 count(mid) k不是 k。我在某次帮朋友排查代码时发现他把条件写成了 count(mid) k导致正确答案总是偏小一位查了半天才发现是边界条件差了一个等号。3. 双指针计数整个题最容易写崩的部分3.1 双指针为什么能算“小于等于 mid 的对数”排序之后数组是升序的这是双指针能用的前提。排序的意义在于对于任意 i jnums[j] - nums[i] 就是这两个数的距离。如果我们固定左端 i然后让右端 j 向右移动直到 nums[j] - nums[i] mid那么从 i1 到 j-1 的所有位置和 i 组成的数对距离都小于等于 mid一共 j - i - 1 个。然后 i 向右移动一格j 不需要回到 i1 重新开始而是继续保持在当前位置或者继续向右。为什么可以这样因为当 i 增大时nums[i] 变大nums[i1] 到 nums[j-1] 与 i1 的距离只会更小j 不会往左退。这就是双指针的滑动窗口本质。我用一个生活化的类比解释想象你在一排递增的数字前面左手固定在一个数上右手往右摸摸到距离超过 mid 就停左手指向的数能和右手之前摸过的所有数组成合法数对。左手往右挪一格右手继续往前摸反正右手指向的数只会越来越大不会回头。整个过程左右手都只往右走每个数字最多被摸两次所以计数是 O(n) 的。这个思路实现起来看起来简单但很多人第一次写会懵主要原因是计数公式到底是 j - i 还是 j - i - 1right 指针初始值应该是 i 还是 i1循环结束条件是 right n 还是 right n这些细节差一点结果就差很多。3.2 三种常见的计数写法与边界分析先放一个通用的逻辑框架def count_pairs(nums, mid): n len(nums) cnt 0 j 0 for i in range(n): while j n and nums[j] - nums[i] mid: j 1 cnt j - i - 1 return cnt这里的 while 循环会把 j 移动到第一个使得 nums[j] - nums[i] mid 的位置也就是 j 指向的是第一个“不合法”的位置。此时从 i1 到 j-1 都合法数量是 j - i - 1。为什么减 1因为 j 比最后一个合法位置多 1减去 i 之后还要把 i 自己排除掉。举个例子nums [1, 2, 3, 4]mid 1。当 i 0nums[i]1j 从 0 开始nums[0] - nums[0] 0 1j 变 1nums[1] - nums[0] 1 1j 变 2nums[2] - nums[0] 2 1循环停止j 2。此时合法位置是 1 和 2 吗不对合法位置是 i11 到 j-11也就是只有下标 1 一个。j - i - 1 2 - 0 - 1 1正确。第二种写法是固定 i让 j 从 i1 开始然后向右移动。代码长这样def count_pairs(nums, mid): n len(nums) cnt 0 j 1 for i in range(n): if j i: j i 1 while j n and nums[j] - nums[i] mid: j 1 cnt j - i - 1 return cnt这种写法多了很多边界处理实际上没必要。第三种写法是让 j 从 0 开始但不使用 j - i - 1而是用另一个变量维护窗口大小有些炫技不推荐。三种写法里第一种最简洁逻辑最容易验证。j 初始化为 0 不会影响正确性因为 while 循环会先把 j 增加到合理位置只有在第一次进入循环时 i0 时 j0 会导致 nums[j]-nums[i]0 计入一个“自身对”但随后 j 会移动到 1实际最终计数时 j - i - 1 把自身排除了。你可以在纸上跑一遍会发现结果完全正确。3.3 边界偏移量j-i-1 还是 j-i为什么会错很多人的 bug 出在 cnt j - i 上。这个错误特别隐蔽因为有些输入数据下结果是错的有些输入下碰巧是对的。问题在于 j 的含义不统一。如果 while 循环结束后 j 指向的是当前 i 的“第一个非法位置”那么 j - i 会把 i 自己和 j 指向的那个非法位置也算进去吗算进去的只有 i 自己非法位置不在窗口里。但 j - i 得到的数量比合法数量多 1因为把 i 自己加进去了。所以必须减 1。还有一种常见的错误是使用 j - i但是 while 循环条件写成 nums[j] - nums[i] mid严格小于这种情况下结果会漏掉距离恰好等于 mid 的数对。注意题目要求“小于等于”用 才是对的。我在实际写代码时会在 while 条件后面写注释“ mid不是 mid”提醒自己。另外判断 count(mid) 时如果 cnt 已经大于等于 k可以提前退出不需要算完整个数组。这是非常有效的剪枝因为二分过程中 mid 可能很大count 很快就能超过 k提前 return 能省掉大量不必要的遍历。4. 完整代码与复杂度说明4.1 Python 实现把上面的思路整合起来完整代码如下def smallest_distance_pair(nums, k): nums.sort() n len(nums) def count_pairs(mid): cnt 0 j 0 for i in range(n): while j n and nums[j] - nums[i] mid: j 1 cnt j - i - 1 if cnt k: return cnt return cnt left, right 0, nums[-1] - nums[0] while left right: mid left (right - left) // 2 if count_pairs(mid) k: right mid else: left mid 1 return left这个实现有几个点需要说明。第一提前剪枝在 count_pairs 里当 cnt k 时直接返回因为只需要知道“够不够”不需要精确值。第二right 的初始化是 nums[-1] - nums[0]在排序后直接取最大距离比设置一个大数更精确。第三while left right 的循环退出时 left 就是答案不需要再做额外的判断。4.2 Java 实现很多面试场景用 Java我也写一版public int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); int n nums.length; int left 0; int right nums[n - 1] - nums[0]; while (left right) { int mid left (right - left) / 2; if (countPairs(nums, mid, k) k) { right mid; } else { left mid 1; } } return left; } private int countPairs(int[] nums, int mid, int k) { int cnt 0; int j 0; int n nums.length; for (int i 0; i n; i) { while (j n nums[j] - nums[i] mid) { j; } cnt j - i - 1; if (cnt k) { return cnt; } } return cnt; }把 k 传入 countPairs 是用于提前退出这样函数语义更清楚。Java 里注意数组排序用的是 Arrays.sort时间复杂度 O(n log n)。int 类型的 cnt 在某些极端数据下可能会超过 2^31-1 吗n 最多 10^5 时cnt 最大是 n(n-1)/2 ≈ 5×10^9确实超过 int 范围所以更稳妥的做法是把 cnt 声明为 long并在 cnt k 时提前返回。如果 n 能到 10^6那 long 也稳。所以 Java 版我习惯把 cnt 写 long避免溢出问题。4.3 复杂度与常数优化排序 O(n log n)。二分循环次数是 O(log M)M 是最大距离。每次二分调用 count_pairs 是 O(n)。总体 O(n log n n log M)。空间复杂度 O(1)只用了几个变量没有额外的大数组。常数优化方面一个是提前退出另一个是局部变量的使用。Python 里 while 循环内部的 nums[j] 和 nums[i] 访问很快不需要额外优化。但要注意每次调用 count_pairs 都重新遍历数组这个遍历本身是 O(n)在整个二分过程中会执行约 log M 次对于 n10^5、M10^9 来说log M 大约 30所以总操作量是 3×10^6 次量级非常快。这里有个细节为什么不是二分“答案”的索引而是二分“数值”因为答案的取值范围是连续的整数从 0 到 max-min直接对数值二分不需要额外的存储。有些类似题目比如“第 k 小的子数组和”也可以套用这个思路但子数组和不能直接对和值二分因为和值可能非常大而距离这个指标天然就是 int 范围内的有限值所以二分非常自然。5. 实战中的坑与排查思路5.1 二分死循环问题二分最怕死循环。left 1、right 2mid 1如果 count(mid) 满足条件让 right mid区间变成 [1, 1]正常退出如果条件不满足让 left mid 1 2区间变成 [2, 2]也正常退出。但如果你把 mid 的计算写成 mid right - (right - left) // 2向上取整并且条件满足时 right mid区间可能会卡住。我调试过一只 bug就是 unknowingly 用了向上取整导致 left 和 right 永远在相邻的两个数之间震荡。规范做法是mid left (right - left) // 2向下取整条件满足时 right mid不满足时 left mid 1。这个组合一定不会死循环。记住这个口诀“向下取整左闭右开收缩”。如果你换成向上取整就必须配套 left mid 和 right mid - 1另一种写法也是对的但新手容易记混不如统一用向下取整。5.2 计数结果溢出与精度问题前面提到 cnt 可能超过 int 上限这是实战中容易忽视的点。Python 的 int 是无限精度问题不大但写 Java 或 C 时建议用 long。除了溢出还有 k 的取值问题。k 最大是 n(n-1)/2所以 k 本身也可能超过 int但题目一般保证 k 是 int 范围内所以你只需要关心 cnt 会不会超过 int。为了保险count_pairs 里 cnt 遇到 k 直接返回这样实际上 cnt 永远不会真正累加到最大值只在 k 很接近 n(n-1)/2 的时候可能累加到接近这个值此时用 long 就没错。这也是一个很自然的优化思路我不需要算出一个精确的 count 再来比较而是边算边比较提前返回。5.3 排序与不排序的区别为什么非排序不可不排序能不能用双指针不能。双指针的核心是窗口内元素有序才能通过单调性推断“右侧只要距离超过 mid右指针就不必回退”。如果不排序nums[j] - nums[i] 不是单调的j 没法不回退计数就退化成 O(n^2)。而排序本身 O(n log n) 的代价是可以接受的因为题目没有要求保持原数组顺序任何修改数组的行为都是允许的。如果你在面试中遇到“能不能不排序”的问题可以这样解释排序是为了给双指针一个单调的环境用 O(n log n) 的预处理换取每次 O(n) 的计数是这道题最优解的必要组成部分。还有一个小细节如果数组中存在负数排序后最大距离仍然是 nums[-1] - nums[0]因为最小数在排序后在最前面最大数在最后面绝对差的最大值一定来自这两个数。这个结论在排序后自然成立不需要额外处理。5.4 几个真实踩坑案例我见过朋友写错的一种情况在 count_pairs 里把 j 放在 for 循环外面但每次重新计算时没有把 j 重置为 0。这会导致第二次调用 count_pairs 时 j 延续上一次的位置计数值完全错乱。正确的做法是每次进入 count_pairs 都把 j 初始化为 0。这个 bug 之所以难发现是因为单次调用时结果是对的但二分需要多次调用第二次就出问题。我建议在 count_pairs 函数内部定义 j不要作为参数传进去这样从结构上杜绝这个错误。还有一种情况是在 while 循环条件里先判断 i 和 j 的大小关系比如写成 while j i and nums[j] - nums[i] mid这会导致自身对永远被排除最终结果比正确答案小。其实 j 从 0 开始在 for i 循环中当 i 增大时 j 可能小于等于 i比如 nums 里有大量重复元素时while 条件 nums[j] - nums[i] mid 可能对 j i 也成立j 会先跳过 i不会出现 j i 的情况。所以不需要额外判断 j 和 i 的关系。想通这一点就明白为什么最简写法足够稳。最后分享一个我自己的习惯写完代码后用一个非常小的例子手动走一遍比如 nums [1, 3, 1], k 1排序后变成 [1, 1, 3]然后手算 count(0) 应该等于 1一对相同元素的距离为 0count(1) 等于 2两个 1 的距离是 01 和 3 的距离是 2 1所以只有 1 对不对距离 0 算一对1 和 3 不算所以 count(1) 还是 1。手算能立刻发现边界问题比直接提交省时间。在实际刷题过程中我体会到这类“第 k 小”问题最核心的套路就是“二分答案 计数验证”。一旦你习惯用 count(mid) 的视角去看问题很多看似复杂的题目都能归约到同一个框架里。如果你正在准备面试建议把这一题的三种边界写法都亲手跑一遍再用 [1, 1, 1] 这种全是重复元素的极端用例测一下确认自己的代码不会在重复元素上出错。这样下次再遇到类似题目你就能直接默写出正确框架而不是每次都得现场从零推理边界。