1.题目基本信息

1.1.题目描述

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [x_i, y_i] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的欧式距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

1.2.题目地址

https://leetcode.cn/problems/number-of-boomerangs/description/

2.解题方法

2.1.解题思路

哈希表。枚举中间结点，统计与该点距离相等的节点，并进行两两有序组合。

3.解题代码

python代码

from collections import defaultdict

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        # 思路：哈希表。枚举中间结点，统计与该点距离相等的节点，并进行两两有序组合。
        n = len(points)
        result = 0
        for i in range(n):
            cnts = defaultdict(int)
            for j in range(n):
                d2 = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
                cnts[d2] += 1
            for v in cnts.values():
                result += v * (v - 1)
        return result

c++代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size();
        int result = 0;
        for (int i = 0; i < n; i++) {
            unordered_map<int, int> cnts;
            for (int j = 0; j < n; j++) {
                int d2 = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2);
                cnts[d2]++;
            }
            for (auto &kv: cnts) {
                result += kv.second * (kv.second - 1);
            }
        }
        return result;
    }
};

4.执行结果