教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南以「宫水三叶的刷题日记」系列中的 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.length1 n 500points[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的独立处理固定点i计算i到其余所有点的距离把相同距离的点归为一组若某一距离上有cnt个点则从中任选 2 个作为(j, k)有序对贡献数为cnt × (cnt - 1)对所有距离分组求和并累加到答案。这就是本题的核心计数对象不是距离本身而是同距离点的有序两两组合数。朴素解法分析三层循环为什么超时最直观的暴力做法是枚举所有三元组(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) { MapInteger, 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(vectorvectorint points) { int n points.size(), ans 0; for (int i 0; i n; i) { unordered_mapint, 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 找到更多使用哈希表 模拟思路的题目进行系统性练习。总结回旋镖的数量是一道典型的暴力思路明显但复杂度不达标的题目其价值在于展示用哈希表把 O(n³) 的重复计算降为 O(n²) 的分组统计思想固定中心点i用x² y²代替欧氏距离作为哈希键规避sqrt与浮点误差以{ 距离 : 个数 }形式预统计距离分布用排列公式cnt × (cnt - 1)累加同距离点的有序组合数。该解法在数据范围n 500下以 O(n²) 时间和 O(n) 空间通过且三种主流语言实现均为最简洁的几行代码。掌握固定中心点 距离/斜率哈希表这一范式后可以轻松迁移到直线上点数、检测正方形等一系列平面几何计数问题中。完整题解与代码可见于仓库 447. 回旋镖的数量中等系列文章覆盖 LeetCode 全部无锁题目可按 Tag 分类查阅。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐「宫水三叶的刷题日记」题解LeetCode 554. 砖墙中等——用哈希表统计间隙反解最少穿砖数「宫水三叶的刷题日记」题解LeetCode 554. 砖墙中等——用哈希表统计间隙反解最少穿砖数 本文是「刷穿 LeetCode」系列的第 554 篇题教程文档AlgoNote 题解0447. 回旋镖的数量——以点为轴心、用哈希表统计距离的计数思路AlgoNote 题解0447. 回旋镖的数量——以点为轴心、用哈希表统计距离的计数思路 本文基于「算法通关手册」AlgoNote中 0447. 回旋镖的教程文档知识库LeetCode 500. 键盘行简单模拟 哈希表打表解法全解析宫水三叶刷题日记系列LeetCode 500. 键盘行简单模拟 哈希表打表解法全解析宫水三叶刷题日记系列 本篇技术指南以「刷穿 LeetCode」系列第 500 篇题教程文档上一篇一张状态转移表塞进一个 Int32chardet4cj PkgInt 位压缩技术全解析下一篇AutoClicker项目架构完整剖析:从WPF界面视图到核心工具类的C代码结构解读创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考