LeetCode 447 - 回旋镖的数量

摘要

这一题是典型的几何 + 哈希表计数问题，属于 LeetCode 算法里的中等偏简单类型。但真正理解它的本质，会让你在之后处理“点对点距离分类”“组合数计算”这类题时变得非常轻松。

题目要求我们统计二维平面里的所有“回旋镖”数量。只要三个点中的两个点与中心点的距离一样（而且顺序不同算不同），就能形成一个有效的回旋镖。

我们会从直觉出发，用一种非常贴近开发者思维的方式讲清楚解法，并给出 Swift 可运行 Demo 代码。

描述

你会拿到一个 n 个点组成的数组，每个点是[x, y]。如果从一个点 i 出发，有两个不同的点 j、k 到它的距离相同，那么(i, j, k)就构成一个回旋镖，而且顺序不同的是不同的回旋镖。

比如：

points = [[0,0],[1,0],[2,0]]

以(1,0)为中心点：

• 和(0,0)距离是 1
• 和(2,0)距离也是 1

所以(1,0) -> (0,0) -> (2,0)和(1,0) -> (2,0) -> (0,0)都是回旋镖，总共2 个。

题解答案

核心逻辑很简单：

1. 选一个点作为“中心点 i”

2. 计算它到所有其他点的距离

3. 把相同距离的点统计在一起

   • 比如对 i 来说，有 3 个点距离都相同

4. 假设某个距离下有m个点

   • 这些点能构成m * (m - 1)个回旋镖
     因为(i, j, k)和(i, k, j)都算合法

然后把所有 i 当作中心点统计即可。

题解代码分析

下面给出的 Swift 代码是可直接运行的版本。

importFoundationclassSolution{funcnumberOfBoomerangs(_points:[[Int]])->Int{letn=points.countifn<3{return0}varresult=0foriin0..<n{vardistanceCount=[Int:Int]()forjin0..<n{ifi==j{continue}letdx=points[i][0]-points[j][0]letdy=points[i][1]-points[j][1]letdist=dx*dx+dy*dy// 用平方距离即可distanceCount[dist,default:0]+=1}// 对每个距离进行组合计数for(_,count)indistanceCount{ifcount>1{result+=count*(count-1)}}}returnresult}}// MARK: - Demo 代码（可运行）letsolution=Solution()print("示例 1：",solution.numberOfBoomerangs([[0,0],[1,0],[2,0]]))// 2print("示例 2：",solution.numberOfBoomerangs([[1,1],[2,2],[3,3]]))// 2print("示例 3：",solution.numberOfBoomerangs([[1,1]]))// 0

题解代码分析（深入讲讲思路）

为什么使用平方距离？

我们并不需要开方，因为只要相等即可，平方距离能减少浮点误差，也让计算更快。

为什么需要用字典统计？

因为以某个点 i 为中心，我们要知道：

• 和它距离相同的点数量是多少？

例如 i 到三个不同点距离为 5：

count = 3 可构成 3 * 2 = 6 个回旋镖 (i,j,k), (i,k,j) ... 等

为什么是count * (count - 1)？

因为这是排列数，不是组合。

顺序不同算不同（题目强调了元组顺序重要）。

示例测试及结果

示例 1

输入：[[0,0],[1,0],[2,0]] 输出：2 解释： 中心点 (1,0) 和其他两个点距离相等 所以 (i,j,k)、(i,k,j) 两种排列

示例 2

输入：[[1,1],[2,2],[3,3]] 输出：2 解释： 所有点呈现对角线方向 每个点与其他两点等距（斜率一致）

示例 3

输入：[[1,1]] 输出：0 解释：单点无法构成任何回旋镖

以上示例已包含在 Demo 代码里，可直接运行验证。

时间复杂度

O(n²)

原因：

• 对每个点 i（共有 n 个）
• 遍历所有点 j（每次 n 次）
• 总共 n² 操作

空间复杂度

O(n)

因为我们用一个字典记录与中心点的距离统计，最坏情况下记录 n−1 个距离。

总结

这道题看似几何题，其实本质是“基于中心点的等距离分组 + 排列数统计”，属于非常典型的哈希计数思想。

你可以从这题总结几个通用技巧：

1. 只要是几何题里要求判断距离是否相等，就用平方距离代替真正距离。
2. 当题目中顺序重要时，通常是排列问题，count * (count - 1)是常客。
3. 对每个点单独作为中心点做统计，是一种很高效的枚举方式。

在实际工程里，如果你在做地图平台、运动分析、用户定位聚类、甚至是某些推荐系统的空间距离处理时，这类“距离分类统计”的思想都能派上用场。