LeetCode-Go 题解 719：Find K-th Smallest Pair Distance 二分答案 + 双指针计数

LeetCode-Go 题解 719：Find K-th Smallest Pair Distance 二分答案 + 双指针计数

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本题来自 LeetCode 第 719 题「Find K-th Smallest Pair Distance」（Hard），要求在一个整数数组中找出所有数对距离（绝对差）中第 k 小的那一个。本仓库 LeetCode-Go 以 Go 实现了该题的标准解法：先排序，再对距离值域做二分搜索，配合双指针在 O(n) 内统计小于等于某个阈值的数对个数。读完本文你将掌握"第 k 小问题转二分判定"的通用套路，以及如何在排序数组上用双指针高效统计差值对数量，并能直接对照仓库内的完整源码与测试用例进行验证。

题目定义

给定一个整数数组nums，返回所有数对之间第 k 小的距离。数对(A, B)的距离定义为A与B的绝对差值。

示例 1：

Input: nums = [1,3,1] k = 1 Output: 0

解释：数组的所有数对及其距离为：

• (1,3) -> 2
• (1,1) -> 0
• (3,1) -> 2

排序后距离序列为[0, 2, 2]，第 1 小的距离是(1,1)对应的0。

题目约束（Note）：

1. 2 <= len(nums) <= 10000
2. 0 <= nums[i] < 1000000
3. 1 <= k <= len(nums) * (len(nums) - 1) / 2

第三个约束说明 k 的取值范围覆盖了全部n*(n-1)/2个数对（含重复组合），因此答案必然存在。注意：两两元素之差可能重复，重复的差值要按多个计数，不去重，这一点直接决定了计数函数的写法。

解题思路：二分答案 + 判定函数

为什么不能直接枚举

n最大可达 10000，数对总数为n*(n-1)/2 ≈ 5×10^7。若把所有差值全部枚举出来再排序取第 k 小，空间和时间都无法承受。因此需要换一个角度：不直接求第 k 小的距离，而是猜测一个距离mid，然后判定"距离 ≤ mid 的数对有多少个"——这就是经典的"二分答案 + 判定"（Binary Search on Answer）模式。

二分区间如何确定

先将原数组排序（排序不改变数对绝对差的值），则：

• 最小可能距离是0（相同元素或相邻元素相减）；
• 最大可能距离是nums[len(nums)-1] - nums[0]（首尾之差）。

于是答案在闭区间[0, nums[len(nums)-1] - nums[0]]内搜索。每次取mid，统计距离不超过mid的数对个数cnt(mid)：

• 若cnt(mid) >= k，说明第 k 小的距离 ≤mid，收缩右边界high = mid；
• 否则说明第 k 小的距离 >mid，提升左边界low = mid + 1。

当low == high时即为答案。cnt(mid)关于mid单调不减，这正是二分可用的前提。核心难点因此转化为：如何在有序数组上高效计算满足nums[j] - nums[i] ≤ mid的数对总数。

源码实现：主函数与两种计数法

仓库完整实现位于 719. Find K-th Smallest Pair Distance.go，全文约 45 行，包含主函数与两种计数实现。

主函数：二分框架

func smallestDistancePair(nums []int, k int) int { sort.Ints(nums) low, high := 0, nums[len(nums)-1]-nums[0] for low < high { mid := low + (high-low)>>1 tmp := findDistanceCount(nums, mid) if tmp >= k { high = mid } else { low = mid + 1 } } return low }

实现要点：

• 先sort.Ints(nums)排序，为后续双指针计数打基础；
• 二分区间初始化为[0, 最大值差]；
• mid := low + (high-low)>>1用移位代替除法，且可避免(low+high)溢出；
• 判定条件采用tmp >= k时收缩右边界，这是"找第 k 小"的标准写法，保证最终落在第一个满足cnt(答案) >= k的距离上，即恰为第 k 小的距离。

解法一（本题正解）：双指针计数

// 解法一 双指针 func findDistanceCount(nums []int, num int) int { count, i := 0, 0 for j := 1; j < len(nums); j++ { for nums[j]-nums[i] > num && i < j { i++ } count += (j - i) } return count }

原理详解：

数组有序后，固定右指针j，需要统计所有满足nums[j] - nums[i] <= num的左端点i的个数。由于数组单调不减，当j增大时，满足条件的i的起始位置只会单调右移（nums[j]变大，若仍要差值不超过num，i只能往右移动），因此可以用一个滑动窗口：

• 内层for循环把i向右推进，直到nums[j]-nums[i] <= num或i == j；
• 此时下标区间[i, j-1]内任意一个元素作为左端点，与nums[j]组成的数对距离都不超过num，共有j - i个；
• 累加进count。

i全程最多移动 n 次，j移动 n 次，所以单次计数复杂度为O(n)。整个算法是sort O(n log n)+ 二分O(log(maxDiff) × n)。

解法二：暴力计数（参照/校验用）

// 解法二 暴力查找 func findDistanceCount1(nums []int, num int) int { count := 0 for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { if nums[j]-nums[i] <= num { count++ } } } return count }

这是最容易理解的两重循环写法，直接枚举所有(i, j)组合并判断nums[j]-nums[i] <= num，时间复杂度O(n²)。虽然正确，但在n = 10000时约 5×10^7 次判断，且该计数在二分过程中会被调用约 20 次（log(maxDiff) ≈ log(10^6) ≈ 20），总开销约 10^9 级别，无法通过。仓库中保留它主要用于正确性对照：测试用例里专门断言了双指针计数与暴力计数的结果一致，详见下文测试章节。

正确性验证：测试用例解析

对应测试文件为 719. Find K-th Smallest Pair Distance_test.go，包含 5 组用例，覆盖了多种边界与一般情形：

用例亮点：

• [1, 1, 1]验证全等元素时所有距离均为 0 的退化情形；
• [1, 6, 1]（排序后[1, 1, 6]）验证重复元素与中等差值混合的排序场景；
• 最后一个 10 元素用例验证较大规模输入下算法的正确性。

测试代码在每次调用后还执行了双指针计数与暴力计数的交叉校验（测试文件）：

if c1, c2 := findDistanceCount(p.num, a.one), findDistanceCount1(p.num, a.one); c1 != c2 { t.Fatalf("distance count mismatch for %v, num=%v: %v vs %v", p.num, a.one, c1, c2) }

这保证了 O(n) 双指针计数与朴素枚举在已排序数组上对同一距离阈值的计数结果严格一致，从测试层面佐证了滑动窗口实现的正确性。

仓库根目录的 coverage.txt 显示，该文件所有函数块（主函数与两种计数函数）均被测试覆盖到，符合本仓库"100% test coverage"的工程约定；仓库的 gotest.sh 使用go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...一次性对全部题解包做覆盖率统计，说明所有 leetcode 子目录题目均以同一套测试流程保障。

本地运行测试

在仓库根目录执行：

go test ./leetcode/0719.Find-K-th-Smallest-Pair-Distance/...

即可单独运行本题测试；或执行仓库根目录的./gotest.sh运行全部题解测试并生成覆盖率文件。测试通过时会输出：

------------------------Leetcode Problem 719------------------------ 【input】:[1 3 1] 【output】:0 ...

复杂度与正确性小结

正确性由"二分区间单调性 + 计数函数精确性"双重保证：cnt(mid)随mid单调不减，因此第一个满足cnt(mid) >= k的mid正是第 k 小的距离；双指针计数在有序数组上精确统计了所有nums[j]-nums[i] <= mid的组合，且经暴力法逐用例交叉验证。

延伸：同一套路的相关题目

"二分答案 + 判定"以及"有序数据中找第 k 小元素"是本仓库中反复出现的题型，与本题同属一个系列的还包括：

• 373. Find K Pairs with Smallest Sums：两个有序数组中找和最小的 k 个数对；
• 378. Kth Smallest Element in a Sorted Matrix：有序矩阵中找第 k 小元素；
• 668. Kth Smallest Number in Multiplication Table：乘法表中找第 k 小数字；
• 786. K-th Smallest Prime Fraction：素数分数数组中找第 k 小分数。

这组题目共同的思维模型是：当"直接构造并排序所有候选"不可行时，转而对答案值域二分，把"求第 k 小"转化为"统计 ≤ mid 的个数"这一可高效计算的判定问题。本题的双指针计数正是这一模型在"有序数组差值对"上的具体落地，掌握它即可举一反三应对上述系列题。

参考文件索引

• 题解说明文档：README.md
• Go 完整实现（双指针 + 暴力计数）：719. Find K-th Smallest Pair Distance.go
• 测试用例与双指针/暴力交叉校验：719. Find K-th Smallest Pair Distance_test.go
• 覆盖率证据：coverage.txt
• 全仓测试脚本：gotest.sh

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go