文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 题解代码分析（深入讲讲思路）
- 为什么使用平方距离？
- 为什么需要用字典统计？
- 为什么是 `count * (count - 1)`？
- 示例测试及结果
- 示例 1
- 示例 2
- 示例 3
- 时间复杂度
- O(n²)
- 空间复杂度
- O(n)
- 总结
摘要
这一题是典型的几何 + 哈希表计数问题，属于 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 个。
题解答案
核心逻辑很简单：
选一个点作为“中心点 i”
计算它到所有其他点的距离
把相同距离的点统计在一起
- 比如对 i 来说，有 3 个点距离都相同
假设某个距离下有
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 个距离。
总结
这道题看似几何题，其实本质是“基于中心点的等距离分组 + 排列数统计”，属于非常典型的哈希计数思想。
你可以从这题总结几个通用技巧：
- 只要是几何题里要求判断距离是否相等，就用平方距离代替真正距离。
- 当题目中顺序重要时，通常是排列问题，
count * (count - 1)是常客。 - 对每个点单独作为中心点做统计，是一种很高效的枚举方式。
在实际工程里，如果你在做地图平台、运动分析、用户定位聚类、甚至是某些推荐系统的空间距离处理时，这类“距离分类统计”的思想都能派上用场。
