LeetCode 447 回旋镖的数量：用哈希表按距离统计组合数（宫水三叶刷题日记题解详解）

• 教程
• 文档

本篇技术指南以「宫水三叶的刷题日记」系列中的 447. 回旋镖的数量（中等） 题解为核心，完整讲解「哈希表 + 模拟」解法：如何将平面上「距离相等三元组」的计数问题，转化为以固定点为中心的 O(n²) 距离统计，并给出 Java、C++、Python 三种可直接提交运行的实现。读完本文，你将掌握「固定中心点 + 距离哈希表」这一处理平面点计数问题的通用范式，并能将其迁移到直线上点数、检测正方形等同类题目中。

题目描述与示例

这是 LeetCode 上的 447. 回旋镖的数量，难度为中等。Tag：「哈希表」「模拟」。

给定平面上n对互不相同的点points，其中points[i] = [xi, yi]。

回旋镖是由点(i, j, k)表示的元组，其中i和j之间的距离和i和k之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

示例 1：

输入：points = [[0,0],[1,0],[2,0]] 输出：2 解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

输入：points = [[1,1],[2,2],[3,3]] 输出：2

示例 3：

输入：points = [[1,1]] 输出：0

提示：

• n = points.length
• 1 <= n <= 500
• points[i].length = 2
• -10^4 <= xi, yi <= 10^4
• 所有点都互不相同

从示例 1 可以看出本题计数的一个关键特性：元组是有顺序的。三个共线点[0,0]、[1,0]、[2,0]中，以[1,0]为i（即回旋镖的"顶点"）时，它到左右两点的距离都为 1，因此(j, k)的排列有( [0,0], [2,0] )和( [2,0], [0,0] )两种，恰好对应题目要求的两个回旋镖。

问题转化：回旋镖计数的本质

回旋镖三元组(i, j, k)的定义可以抽象为：以i为公共端点，j与k到i的距离相等。

换句话说，我们并不是在统计任意三个点的关系，而是固定住第一个点i，考察它与其他所有点的距离分布。因此，整个计数过程天然可以被拆解为对每个点i的独立处理：

1. 固定点i；
2. 计算i到其余所有点的距离；
3. 把相同距离的点归为一组：若某一距离上有cnt个点，则从中任选 2 个作为(j, k)有序对，贡献数为cnt × (cnt - 1)；
4. 对所有距离分组求和，并累加到答案。

这就是本题的核心：计数对象不是"距离"本身，而是"同距离点的有序两两组合数"。

朴素解法分析：三层循环为什么超时

最直观的暴力做法是枚举所有三元组(i, j, k)，逐一判断i到j、i到k的距离是否相等。

数据范围为n <= 500，三层循环的朴素做法复杂度为 O(n³)，最多需要枚举约 500³ ≈ 1.25 亿 个组合，显然会TLE。

同时，朴素做法还存在重复计算：对于同一个点i，它到其他点的距离会被反复计算（每换一个(j, k)组合就要重算一次），完全没有利用"距离相等"这一分组信息。这正是引入哈希表进行预处理的意义所在。

核心解法：以 i 为中心的哈希表统计

算法思想

对于每个回旋镖三元组而言，本质上我们在统计给定i的情况下，与i距离相等的(j, k)组合个数。

我们可以使用哈希表进行预处理：在统计以i为三元组第一位的回旋镖个数前，先计算出i和其余点的距离，并以{ 距离 : 个数 }的形式进行存储，然后分别对所有的距离进行累加计数。

用距离平方代替欧氏距离

在计算距离时，为了避免使用sqrt（既引入了浮点运算开销，又存在浮点比较精度问题），我们直接使用x² + y²来代指两点间的距离。

设两点坐标为(x1, y1)与(x2, y2)，则：

dist = (x1 - x2)² + (y1 - y2)²

由于题目坐标范围是-10^4 <= x, y <= 10^4，坐标差最大为2 × 10^4，平方后最大值为4 × 10^8，两数之和最大为8 × 10^8，完全在 32 位整数范围内，无需担心溢出问题。同时，x² + y²与真实距离sqrt(x² + y²)具有严格的单调对应关系：两个距离相等当且仅当它们的平方相等，因此用平方值作为哈希表的键完全等价且更安全。

计数公式 cnt × (cnt - 1) 的推导

当固定点i后，若某个距离值上有cnt个点，则以i为顶点、以这cnt个点中的任意两个为(j, k)的有序组合数为排列数：

P(cnt, 2) = cnt × (cnt - 1)

之所以是排列而不是组合，是因为题目明确"需要考虑元组的顺序"：(i, j, k)与(i, k, j)视为两个不同的回旋镖。这一点与示例 1 的输出结果完全吻合。

Java 代码

class Solution { public int numberOfBoomerangs(int[][] points) { int n = points.length; int ans = 0; for (int i = 0; i < n; i++) { Map<Integer, Integer> map = new HashMap<>(); for (int j = 0; j < n; j++) { if (i == j) continue; int x = points[i][0] - points[j][0], y = points[i][1] - points[j][1]; int dist = x * x + y * y; map.put(dist, map.getOrDefault(dist, 0) + 1); } for (int dist : map.keySet()) { int cnt = map.get(dist); ans += cnt * (cnt - 1); } } return ans; } }

C++ 代码

class Solution { public: int numberOfBoomerangs(vector<vector<int>>& points) { int n = points.size(), ans = 0; for (int i = 0; i < n; i++) { unordered_map<int, int> distCount; for (int j = 0; j < n; j++) { if (i == j) continue; int x = points[i][0] - points[j][0], y = points[i][1] - points[j][1]; int dist = x * x + y * y; distCount[dist]++; } for (auto& [d, cnt] : distCount) ans += cnt * (cnt - 1); } return ans; } };

Python 代码

class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int: ans = 0 for i in range(len(points)): cnt = defaultdict(int) for j in range(len(points)): if i == j: continue x, y = points[i][0] - points[j][0], points[i][1] - points[j][1] dist = x * x + y * y cnt[dist] += 1 for v in cnt.values(): ans += v * (v - 1) return ans

三种语言的实现逻辑完全一致：外层循环固定中心点i，内层循环统计i到其他各点的距离平方并写入哈希表，最后遍历哈希表用cnt × (cnt - 1)累加答案。Python 实现需要引入collections.defaultdict以避免KeyError。

复杂度分析

• 时间复杂度：O(n²)。外层需要遍历n个中心点，内层对每个中心点遍历其余n - 1个点并做 O(1) 的哈希表读写，因此总复杂度为 O(n²)。
• 空间复杂度：O(n)。每个中心点i维护一张距离哈希表，最坏情况下i到其余点的距离互不相同，哈希表最多存储n - 1个键值对。

对于n <= 500的数据范围，O(n²) ≈ 25 万 次距离计算，性能绰绰有余。

易错点与边界情况

• 跳过自身：内层循环中必须if (i == j) continue;，否则i到自身的距离 0 会被计入，从而错误地把(i, i, k)甚至(i, i, i)这类非法元组算进答案。
• 只有 1 个点：示例 3 中points = [[1,1]]输出 0，因为不存在第二个点，任何距离分组都无法凑出(j, k)组合，cnt - 1 = 0的乘法自然保证结果为 0。
• n = 2 的情况：两个点只能构成(i, j)，缺少第三个点，答案同样为 0，上述代码无需特判即可正确处理。
• 坐标对称性：距离公式(x1 - x2)² + (y1 - y2)²中差值的符号不影响平方结果，因此i到j与j到i的距离天然一致，无需额外处理。

同类题目的延伸：固定中心点 + 哈希表范式

本题的"固定一个点，用哈希表统计到其他点的某个度量值"思路，是处理平面点计数问题的高频通用范式。在 LogicStack-LeetCode 仓库中，可以找到多道应用同一思路的题目，印证这一模式的价值：

149. 直线上最多的点数（困难）

在 149. 直线上最多的点数（困难） 中，同样是枚举每个点作为中心，但哈希表的键从"距离"换成了"斜率"：固定点i后，用{ 斜率 : 个数 }统计经过i的各方向直线上的点数。与本题不同的是，斜率需要借助gcd约分并序列化为字符串键来避免浮点精度问题——这正是"距离用平方、斜率用约分"两种规避浮点误差的经典手法，可以对比阅读。

2013. 检测正方形（中等）

在 2013. 检测正方形（中等） 中，题目要求统计与查询点构成轴对齐正方形的方案数，其解法使用"哈希表套哈希表"（{x, {y : 数量}}）存储点集，再通过枚举同x行的点求出边长len，检查另外两个顶点的出现次数并应用乘法原理。这里同样体现了"由已知点推导几何约束 + 哈希表计数"的组合，是本题思路在更高维度（二维嵌套哈希表）上的延伸。

1037. 有效的回旋镖（简单）

注意区分的是 1037. 有效的回旋镖（简单）：该题定义"回旋镖"为三个各不相同且不共线的点，属于纯粹的几何判定问题（用向量叉积是否为 0 判断三点是否共线，O(1) 时间），与本题"距离相等的有序三元组计数"在定义和算法上都不同。两者名称相近但考察点迥异，刷题时注意不要混淆。

上述题目均收录于 哈希表专题索引，可以按 Tag 找到更多使用"哈希表 + 模拟"思路的题目进行系统性练习。

总结

447. 回旋镖的数量是一道典型的"暴力思路明显但复杂度不达标"的题目，其价值在于展示用哈希表把 O(n³) 的重复计算降为 O(n²) 的分组统计思想：

448. 固定中心点i，用x² + y²代替欧氏距离作为哈希键，规避sqrt与浮点误差；

449. 以{ 距离 : 个数 }形式预统计距离分布；

450. 用排列公式cnt × (cnt - 1)累加同距离点的有序组合数。

该解法在数据范围n <= 500下以 O(n²) 时间和 O(n) 空间通过，且三种主流语言实现均为最简洁的几行代码。掌握"固定中心点 + 距离/斜率哈希表"这一范式后，可以轻松迁移到直线上点数、检测正方形等一系列平面几何计数问题中。完整题解与代码可见于仓库 447. 回旋镖的数量（中等），系列文章覆盖 LeetCode 全部无锁题目，可按 Tag 分类查阅。

• 教程
• 文档