LeetCode 447. 回旋镖的数量

2024-01-16 HGNULB 约 9 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 447. 回旋镖的数量

题意分析

题目目标：给定平面上一组互不相同的点，统计满足条件的有序三元组 (i, j, k) 的个数，条件是 i 到 j 的距离等于 i 到 k 的距离。返回这样的三元组总数。
核心约束：题目明确说三元组是有序的，也就是 (i, j, k) 和 (i, k, j) 算作两个不同的答案，这直接决定了计数公式里用的是排列数而非组合数。三元组的第一个位置 i 扮演的是「顶点」角色，另外两个点只需要到它等距——这说明约束是围绕某一个中心点展开的，可以按中心点把整个问题拆成互不重叠的子问题。点的数量上界只有 500，$n^2$ 是二十五万，$O(n^2)$ 完全可以接受，而 $O(n^3)$ 的一亿两千万次操作则风险很大。坐标范围在 $\pm 10^4$ 之内，因此距离的平方最大约 $8 \times 10^8$，仍在 32 位整数范围内。
边界处理：点数少于 3 时不可能构成三元组，答案为 0；某个中心点周围可能没有任何两点等距，此时贡献为 0；同一距离只出现一次时贡献也应为 0 而不是 1；点保证互不相同，所以不存在距离为 0 的其他点，但计算时仍要跳过 j 等于 i 自身；距离必须用平方值比较，不能开方。

解法：按距离分组计数

核心思路

直译题意的写法是三重循环：枚举 i、枚举 j、枚举 k，判断两段距离是否相等。这是 $O(n^3)$，在 n 为 500 时约一亿两千五百万次距离计算，虽然常数很小但已经贴近超时线，而且它做了大量重复劳动——同一对 (i, j) 的距离会被重新计算 n 次。
瓶颈的根源是把三个下标当成了平等的三元组来枚举，但它们其实并不平等：i 是顶点，j 和 k 只是「到 i 等距」的两个点。既然如此，就应该先把 i 固定住，把问题降维成「在一堆到 i 的距离里，有多少个有序对的距离相同」。这个子问题只关心距离这一个标量，与点的具体坐标无关。
于是关键观察成型：固定顶点 i 之后，把其余 n-1 个点按到 i 的距离分组，若某个距离恰好有 c 个点，则从这 c 个点里挑出有序对 (j, k) 的方案数是 $c \times (c-1)$。之所以是排列而非组合，正是因为题目要求有序——先挑 j 有 c 种选择，再挑 k 只能从剩下的 c-1 个里选，且 (j, k) 与 (k, j) 都要计入。不同距离组之间不可能配对（距离不等就不满足条件），所以各组贡献直接相加；不同顶点 i 之间也不会重复（三元组的第一个位置唯一确定了顶点），所以各个 i 的结果也直接相加。
对每个固定顶点维护「距离平方 → 已处理点数」的哈希表。加入新点前，若同距离已有 c 个点，新点可与每个旧点按 (旧, 新)、(新, 旧) 两种顺序组成回旋镖，因此立即贡献 2c，再把频次加一。

不变量是：处理完当前顶点的若干邻点后，cnt[d] 等于距离平方为 d 的已处理点数，答案已包含这些点之间的全部有序对。 新点增加 2c 后不变量继续成立；一个桶最终累计的 0 + 2 + ... + 2(c-1) 正好等于 c(c-1)。距离用平方作为整数键，既保持相等关系，又省掉无用的开方。

解题步骤

第一步：外层循环枚举每一个点作为顶点 i，答案累加器初始化为 0。 为什么可以按顶点划分而不会重复或遗漏：每个合法三元组的第一个分量唯一确定了它的顶点，所以它恰好在顶点为该点的那一轮被统计一次，各轮之间是对答案集合的一个划分。

第二步：为当前的 i 新建一张空哈希表，键是距离平方、值是出现次数。 为什么每轮都要新建而不是复用一张表：不同顶点对应完全不同的距离分布，若不清空，上一轮的计数会污染这一轮，导致贡献被严重高估。

第三步：内层循环遍历所有 j，跳过 j 等于 i 的情形，计算 dx = xi - xj、dy = yi - yj，把 dx*dx + dy*dy 作为键累加计数。 为什么必须跳过自己：题目要求三个点两两不同，顶点自己不能充当 j 或 k；如果不跳过，距离 0 会被记一次，虽然 c = 1 时贡献恰好是 0 不影响结果，但语义上不严谨，且在允许重复点的变体题里会直接算错。为什么用平方和作为键而不是先开方：Math.sqrt 返回 double，两个数学上相等的距离在浮点表示下可能相差一个最小精度单位，被哈希成不同的键，导致漏统计；平方值是整数，相等性判断精确无误。为什么不用担心溢出：坐标差最大 $2 \times 10^4$，平方是 $4 \times 10^8$，两项相加约 $8 \times 10^8$，小于 int 的上限约 $2.1 \times 10^9$。

第四步：先执行 answer += 2 * cnt[d2]，再令 cnt[d2]++。 查询在前，保证 cnt 只含此前邻点；每个旧点与新点产生两个有序对。顺序反过来会把新点自己也算入频次，凭空多加 2。

第五步：所有顶点处理完后返回累加结果。 为什么各轮可以直接相加：如前所述，按顶点划分是对答案集合的不重不漏划分，求和即为总数。

以 points = [[0,0],[1,0],[2,0]] 走一遍。 顶点 (0,0) 的两个距离平方为 1、4，加入时频次都为 0，贡献 0；顶点 (1,0) 先看到一个距离平方 1 的点，贡献 0 并记频次 1，再看到另一个同距离点，贡献 2 * 1 = 2；顶点 (2,0) 同样没有重复距离。最终答案为 2，对应交换另外两点顺序得到的两个三元组。

代码实现

import java.util.HashMap;
import java.util.Map;

// 核心实现：按距离分组计数，维护必要状态并避免重复处理。
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int n = points.length;
        int answer = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int j = 0; j < n; j++) {
                if (j == i) {
                    continue;
                }
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                int d2 = dx * dx + dy * dy;
                int same = cnt.getOrDefault(d2, 0);
                answer += 2 * same;
                cnt.put(d2, same + 1);
            }
        }
        return answer;
    }
}

// 核心实现：按距离分组计数，维护必要状态并避免重复处理。
func numberOfBoomerangs(points [][]int) int {
	n := len(points)
	answer := 0
	for i := 0; i < n; i++ {
		cnt := make(map[int]int)
		for j := 0; j < n; j++ {
			if j == i {
				continue
			}
			dx := points[i][0] - points[j][0]
			dy := points[i][1] - points[j][1]
			d2 := dx*dx + dy*dy
			answer += 2 * cnt[d2]
			cnt[d2]++
		}
	}
	return answer
}

复杂度分析

时间复杂度：$O(n^2)$。外层枚举 n 个顶点，每轮遍历其余 n-1 个点，并在加入距离桶时直接结算新增贡献；没有额外的桶遍历。哈希查询与写入按均摊 $O(1)$ 计，因此每轮 $O(n)$。

空间复杂度：$O(n)$。凭什么：每轮只维护一张至多含 n-1 个键的哈希表，处理完立即丢弃，任意时刻存活的额外结构规模都是 $O(n)$，不随枚举轮数累积。

关键点总结

当待统计的元组中存在一个「角色不同」的分量时，优先固定它、把问题降到更低维度。这里顶点 i 与另外两点地位不对等，固定 i 后问题就从三维枚举塌缩成一维的频次统计，复杂度直接掉一个数量级。

「从 c 个等价元素中选出有序对」的方案数是 $c(c-1)$，选出无序对是 $c(c-1)/2$。看清题目要的是有序还是无序，直接决定答案是否差两倍，这是组合计数题最高频的失分点。

涉及距离、模长的相等性判断，一律用平方值比较，绝不开方。浮点开方引入的舍入误差会让数学上相等的量被判为不等，而平方保持整数运算，既精确又更快。

流式计数时遵守「先贡献、后加频次」：新点只和此前点配对，每个旧点产生两种顺序。累计结果与最终一次计算 c(c-1) 完全等价。

哈希表的生命周期必须绑定当前顶点；换顶点就清空，否则不同中心的距离分组会互相污染。

面试视角：先固定顶点，把三重枚举降成距离频次统计；随后说明平方距离避免开方、c(c-1) 来自有序对。当前约束下 $O(n^2)$ 已足够，不需要为几何结构引入更复杂的数据结构。

易错点总结

错误写法：贡献用组合数 c * (c - 1) / 2。用例 points = [[0,0],[1,0],[2,0]] → 返回 1，而题目要求有序三元组，正确答案是 2。

低效写法：先调用 Math.sqrt 再分组。相等的平方距离本就对应相等距离，开方不提供额外信息；若题目扩展到浮点坐标，还会引入不必要的精度问题。

错误写法：哈希表在外层循环之前创建，每轮不清空。用例 points = [[0,0],[1,0],[2,0]] → 第二个顶点结算时把第一个顶点的距离计数一并算入，得到远大于 2 的结果。

错误写法：把距离平方存进 short 或用 (int) 截断中间结果。用例坐标为 [[-10000,-10000],[10000,10000]] → 距离平方 $8 \times 10^8$ 超出 short 范围被截断，不同距离被映射到同一键，计数虚高。

错误写法：只枚举 j > i 的点对以为能去重。用例 points = [[0,0],[1,0],[2,0]] → 顶点为 (1,0) 时只看到 (2,0) 一个点，计数表为 {1:1}，贡献 0，返回 0 而不是 2；顶点必须能看到所有其他点。

错误写法：把三元组理解成无序集合，最后再除以 2 或乘以 3。用例 points = [[0,0],[1,0],[2,0]] → 任何形式的整体缩放都无法还原正确的有序计数，返回 1 或 6 之类的错值。

错误写法：用 cnt.put(d2, cnt.get(d2) + 1) 而不先处理键不存在的情况。用例任意首次出现的距离 → Java 中 get 返回 null，自动拆箱触发 NullPointerException。

错误写法：先执行 cnt[d2]++ 再累加 2 * cnt[d2]。第一个邻点就会贡献 2，实际此时还没有可配对的旧点；查询必须在自增之前。

错误写法：点数少于 3 时不做任何处理直接返回哈希表大小之类的中间量。用例 points = [[0,0]] → 返回 1 或抛异常，正确答案是 0；实际上主循环对这类输入天然返回 0，无需特判但也不能返回错误的中间值。

相似题目

题目	难度	考察点
149. 直线上最多的点数	困难	同样固定一点再对其余点分组，但分组键是斜率，需要用最简分数避免浮点误差
454. 四数相加 II	中等	把四重枚举拆成两半并用哈希表对接，同为「降维 + 频次统计」的组合计数
973. 最接近原点的 K 个点	中等	同样用距离平方避免开方，重点转为 Top-K 选取而非分组计数
593. 有效的正方形	中等	依靠边长平方的相等关系做几何判定，考察对距离集合的分类讨论
560. 和为 K 的子数组	中等	哈希表统计频次并按「有多少个满足条件的前驱」累加答案，是同一套计数范式