447. 回旋镖数量

🎯 问题描述

描述：
给定平面上 n 个点，其中每个点表示为 points[i] = [xi, yi]。
回旋镖是由三个点组成的元组 (i, j, k)，其中 i、j 和 k 是不同的点，且 i 到 j 的距离与 i 到 k 的距离相等。

计算并返回回旋镖的数量。

说明：

这是一个枚举中心点 + 哈希表计数的问题
核心策略：枚举每个点作为回旋镖的中心点，统计到其他点的距离频次
排列计算：对于距离相同的点，使用乘法原理计算排列数

示例：
示例 1：

输入：points = 
输出：2
解释：
回旋镖为  和 
即以 [1,0] 为中心，到 [0,0] 和 [2,0] 距离相等的两个排列

💻 解题思路

思路1：枚举中心点 + 动态计数

核心逻辑

枚举中心点：
- 遍历每个点作为回旋镖的中心点 i
计算距离频次：
- 对于每个中心点，计算它到其他所有点的距离平方
- 使用哈希表统计相同距离的点的个数
动态计算排列数：
- 关键技巧：在遍历过程中动态累加结果
- 当发现一个新的点与之前某些点距离相等时，立即计算新增的排列数

代码实现

from collections import defaultdict
from typing import List

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        
        # 1. 枚举每一个点作为回旋镖的中心点
        for x1, y1 in points:
            # 哈希表记录距离平方出现的次数
            cnt = defaultdict(int)
            
            # 2. 枚举其他所有点
            for x2, y2 in points:
                # 计算中心点到当前点的距离平方
                d2 = (x1 - x2) ** 2 + (y1 - y2) ** 2
                
                # 3. 核心逻辑：动态计算新增的回旋镖数量
                # cnt[d2] 表示之前已经有多少个点与当前点到中心点的距离相等
                # 每个已存在的点都可以与当前点组成2个不同的回旋镖（顺序不同）
                ans += cnt[d2] * 2
                
                # 4. 将当前距离的计数加1
                cnt[d2] += 1
        
        return ans

# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/number-of-boomerangs/solutions/2595488/jian-ji-xie-fa-fu-xiang-si-ti-mu-pythonj-39p8/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

📊 性能分析

时间复杂度： $O(N^2)$ $O (N^{2})$
- 外层循环枚举中心点： $O(N)$
- 内层循环枚举其他点： $O(N)$
- 哈希表操作平均时间复杂度： $O(1)$
- 总体时间复杂度为 $O(N^2)$
空间复杂度： $O(N)$ $O (N)$
- 哈希表最多存储 $N-1$ 个不同的距离值
- 空间复杂度为 $O(N)$

思考

为什么使用距离平方？
- 为了避免浮点数运算和开根号操作
- 只需要比较距离是否相等，不需要具体距离值
- 距离平方相等 ⇔ 距离相等
动态计数的巧妙之处：
- 传统方法：先统计完所有距离频次，再用公式 $n \times (n-1)$ 计算
- 本解法：边遍历边累加，每次新增点时直接计算贡献
- ans += cnt[d2] * 2 的含义：
  - cnt[d2]：之前有多少个点与当前点距离相等
  - * 2：新点可以放在排列的第二位或第三位
避免重复计数：
- 通过枚举中心点的方式，每个回旋镖只被计算一次
- 顺序不同的元组被视为不同的回旋镖
边界处理：
- 当点数少于3时，无法形成回旋镖
- 哈希表自动处理距离频次统计