回旋镖的数量 图解题解

平面上一堆点，回旋镖 (i,j,k) 讲顺序怎么数

给平面上 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。

把每个三元组都摆出来验，点一多就跑不动

最直接的想法是三层循环，把每个 (i, j, k) 都列出来，逐个验证 i 到 j、i 到 k 距离是否相等。可 n 个点选三个位置就是 n×n×n 量级，时间 O(n³)；点数到几百上千就慢得没法接受。

回旋镖的相等条件，其实全挂在中心那个点上

回旋镖的约束都写在中心 i 头上：i 到 j 的距离等于 i 到 k 的距离，而 j、k 彼此无关。既然只认中心，就固定一个点当中心，量它到其余各点的距离，把等距的点归为一组。某距离上落了 m 个点，从中讲顺序挑出 j、k 两个就凑成一个回旋镖——有序挑两个共 m×(m−1) 种，不除以 2，因为回旋镖分先后。

分组用一张哈希表记「距离 → 点数」，按距离当键直接取值、查一次几乎不花时间，扫一遍就把每个距离的 m 数清。比距离不必开平方根，直接用平方距离（横纵坐标差的平方之和）当键：浮点小数判相等有精度风险，整数平方又快又不比错。

固定中心、量距离、按组累加，三步怎么走

流程钉死三步：挑一个点当中心；另起一张空表遍历其余各点，算它到中心的平方距离、往对应距离的计数加一；中心量完把每个距离的点数 m 取出，累加 m×(m−1) 到答案。再换下一个点当中心重复。每换一个中心都得另起新表，距离相对当前中心算，沿用旧表会把别人计数混进来。n 个点各当一次中心，贡献全加起来就是回旋镖总数。

五个十字点逐个当中心，各贡献多少

先让 (1,1) 当中心：到 (0,1)、(2,1)、(1,0)、(1,2) 的平方距离都是 1，四个点全挤在距离 1 上，m=4，贡献 4×3=12。换 (0,1) 当中心：到 (1,1) 平方距离 1、到 (2,1) 是 4、到 (1,0) 和 (1,2) 都是 2，只有距离 2 上凑了 2 个点，贡献 2×1=2，其余距离各 1 点配不成对。剩下 (2,1)、(1,0)、(1,2) 与 (0,1) 对称，也各在距离 2 上落 2 点、各贡献 2。五个中心加起来 12+2+2+2+2=20，这就是回旋镖的总数。

换中心忘了清表，别人的账全算到你头上

复杂度上，外层每点当中心、内层扫一遍所有点，时间 O(n²)；每个中心一张距离表最多 n 项，空间 O(n)，比枚举三元组的 O(n³) 快一个量级。最阴的坑是换中心时沿用没清空的旧表，前一中心的点数会串进来、把答案抬高。把 m×(m−1) 误写成 m×(m−1)/2，讲顺序的回旋镖就漏掉一半。改用开方后的浮点距离当键，一般情形下相等判断会因精度抖动误分组。点数少于三个时任何中心都配不出一对，答案为 0；各点到中心距离两两不同、每组仅 1 点时 m×(m−1)=0，同样不贡献。

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 << 1

C++

#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;
    }
}