LeetCode 447. 回旋镖的数量，枚举+哈哈希

一、题目

1、题目描述

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

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

2、接口描述

?

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {

    }
};

3、原题链接

447. 回旋镖的数量

二、解题报告

1、思路分析

可见符合条件的三个点构成了一个等腰三角形，那么我们固定一个点，去计算和其它所有点的距离，对于距离为k的点的数目由m个，那么就加上A(2 , m)，固定每个点然后计算一次即可

2、复杂度

时间复杂度：O(n^2) 空间复杂度：O(n)

3、代码详解

?

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
       int ret = 0;
       for(auto& x : points)
       {
            unordered_map<int , int> hash;

            for(auto& y : points)
            hash[(x[0] - y[0]) * (x[0] - y[0]) + (x[1] - y[1]) * (x[1] - y[1])]++;
            for(auto [_ , m] : hash)
            ret += m * (m - 1);
       }
       return ret;
    }
};