LeetCode 447中等数组 · 哈希
回旋镖的数量 图解题解
这道题到底在问什么
给定平面上 n 个互不相同的点 points。回旋镖是元组 (i, j, k)，满足 i 到 j 的距离等于 i 到 k 的距离。元组讲顺序，(i,j,k) 与 (i,k,j) 算两个。返回回旋镖总数。
- 输入
- points = [(1,1),(0,1),(2,1),(1,0),(1,2)]
- 输出
- 20
最优解：一步一步想明白
- 3口诀记牢：每个点轮流当中心，按距离把其余点分组，某距离上有 m 个点就贡献 m×(m−1)。下面每一帧都在套它。
- 4先固定第 0 个点 (1,1) 当中心（紫色）。接下来量它到另外 4 个点的距离，按距离分组记到右边的距离表里。
- 5量到第 1 个点 (0,1)（绿色），平方距离是 1。距离 1 第一次出现，登记 1 个点。
- 6量到第 2 个点 (2,1)（绿色），平方距离是 1。距离 1 又来一个，现在这条距离上累计 2 个点，它们彼此能和中心配成回旋镖。
- 7量到第 3 个点 (1,0)（绿色），平方距离是 1。距离 1 又来一个，现在这条距离上累计 3 个点，它们彼此能和中心配成回旋镖。
- 8量到第 4 个点 (1,2)（绿色），平方距离是 1。距离 1 又来一个，现在这条距离上累计 4 个点，它们彼此能和中心配成回旋镖。
- 9中心 (1,1) 量完：四个点全落在距离 1 上，m = 4。讲顺序地从这 4 个里挑两个，共 4×3 = 12 个回旋镖。答案累计到 12。
- 10换第 1 个点 (0,1) 当中心。注意每换一个中心，距离表都要清空重来，距离是相对当前中心算的。
- 11量到 (1,1)，平方距离 1。距离 1 记 1 个。
- 12量到 (2,1)，平方距离 4。距离 4 记 1 个。
- 13量到 (1,0)，平方距离 2。距离 2 记 1 个。
- 14量到 (1,2)，平方距离 2。距离 2 这下凑到 2 个点了，它们能和中心 (0,1) 组成回旋镖。
- 15中心 (0,1) 量完：只有距离 2 上落了 2 个点，贡献 2×1 = 2，别的距离各只 1 个点配不成对。答案累计到 14。
- 16第 3 个中心 (2,1)，流程一样：清空距离表，逐个量距离。
- 17量到 (1,1)，平方距离 1，距离 1 累计 1 个点。
- 18量到 (0,1)，平方距离 4，距离 4 累计 1 个点。
- 19量到 (1,0)，平方距离 2，距离 2 累计 1 个点。
- 20量到 (1,2)，平方距离 2，距离 2 累计 2 个点。
- 21中心 (2,1) 同样在距离 2 上凑到 2 个点，贡献 2。答案累计到 16。
- 22第 4 个中心 (1,0) 和前面对称，过程一样，直接看分组结果：距离 1: 1 个点，距离 2: 2 个点，距离 4: 1 个点。
- 23中心 (1,0) 在距离 2 上有 2 个点，贡献 2。答案累计到 18。
- 24第 5 个中心 (1,2) 和前面对称，过程一样，直接看分组结果：距离 1: 1 个点，距离 2: 2 个点，距离 4: 1 个点。
- 25中心 (1,2) 在距离 2 上有 2 个点，贡献 2。答案累计到 20。
- 26五个点各当一次中心，把贡献全加起来：中心 (1,1) 贡献 12，另外四个各贡献 2，合计 20。这就是答案。
⚠️ 容易写错的地方
✗ 错：按 m×(m−1)/2 算（当成无序对）
✓ 对：用 m×(m−1)（有序对）
回旋镖 (i,j,k) 与 (i,k,j) 算两个，讲顺序就不除以 2
✗ 错：一般情况下用开方后的欧式浮点距离当键
✓ 对：推荐用平方距离的整数当键
浮点距离的相等判断在一般情形有精度风险，平方整数键又快又稳（本题整点坐标恰好让浮点比较也安全）
✗ 错：换中心时忘了清空距离表
✓ 对：每个中心独立建一张新表
距离是相对当前中心算的，混用会把别的中心的计数算进来
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
ans = 0
for p1 in points:
cnt = Counter()
for p2 in points:
d = dist(p1, p2)
ans += cnt[d]
cnt[d] += 1
return ans << 1C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
int ans = 0;
for (auto& p1 : points) {
unordered_map<int, int> cnt;
for (auto& p2 : points) {
int d = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
ans += cnt[d];
cnt[d]++;
}
}
return ans << 1;
}
};Java
import java.util.*;
class Solution {
public int numberOfBoomerangs(int[][] points) {
int ans = 0;
for (int[] p1 : points) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int[] p2 : points) {
int d = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
ans += cnt.getOrDefault(d, 0);
cnt.merge(d, 1, Integer::sum);
}
}
return ans << 1;
}
}复杂度
时间
O(n²)
每个点当一次中心，各自再扫一遍所有点
空间
O(n)
每个中心一张距离哈希表，最多 n 项
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 回旋镖的数量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么枚举「中心点」而不是枚举点对，能从 O(n³) 降到 O(n²)？+
回旋镖的约束全挂在中心 i 上：i 到 j、i 到 k 距离相等。固定中心 i 后，问题就变成「在到 i 距离相同的点里有序挑两个」，用一张哈希表按距离分组，一次扫描就能数出所有合法的 j、k 组合，省掉了对 j、k 的第三层枚举。
这题还能更快吗？+
很难。答案本质要统计每个中心上同距离点的成对情况，至少得把每个点到其余点的关系看一遍，O(n²) 已是这类「按距离配对」问题的实际下界，哈希分组是最优级别的做法。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 回旋镖的数量 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。