题目描述

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

找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

样例

输入：[[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

算法

(哈希表) $O(n^2)$

1. 枚举 $i$，然后遍历所有的回旋镖，计算距离并用哈希表记录每种距离的出现次数。

时间复杂度

• 假设哈希表单次操作的时间复杂度为常数，总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        const int n = points.size();
        int ans = 0;
        for (const auto &p : points) {
            unordered_map<int, int> tot;
            for (const auto &q : points) {
                int d = (p[0] - q[0]) * (p[0] - q[0]) +
                    (p[1] - q[1]) * (p[1] - q[1]);
                ans += tot[d];
                tot[d]++;
            }
        }
        return ans * 2;
    }
};