每日一题_447.回旋镖的数量

leetcode 447

题目：

题意分析：
今天的题目比较简单，没有复杂的算法，主要是用空间换时间。该题是给我们平面上一系列的点，这些点都在整数格点上，然后当其中一个点到另外两个不重复的点的欧几里得距离相等，那么这三个点就构成一个回旋镖，其实就是类似一个 “ V ”行，所以叫 “ 回旋镖 ” 嘛。而题目就是让我们求平面上所有的点中，构成的回旋镖的个数。

算法（哈希表）：
首先这道题如果暴力枚举的话，因为是三个点，所以是三层循环，n最大是500，那么500^3 = 1.25 * 1e8 > 1e8，所以时间复杂度爆了。因此，需要优化。再回去读题，对于当前的一个点，我们关心的其实是其他点到当前点的距离，然后能和当前点构成回旋镖的点必然同属于一个集合，就是距离相等的点构成一个集合，然后不同距离的点就是不同的集合，其次我们并不关心每个集合中的具体的元素，只要知道集合中元素的个数，排列就可以得到能和当前点构成回旋镖的数量了。鉴于以上分析，我们可以采用Hash表数据结构，遍历平面上所有点，然后对每一个点，计算其他的点到该点的距离，并用map来记录每个距离的点的个数。最后A(2, k)排列即可得到结果。

代码：

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for (auto cur_point: points)
        {
            int x_i = cur_point[0], y_i = cur_point[1];
            unordered_map<int, int> mp;
            for (int i = 0; i < points.size(); i ++)
            {
                int x_j = points[i][0], y_j = points[i][1];
                int dist = (x_i - x_j) * (x_i - x_j) + (y_i - y_j) * (y_i - y_j);
                ++ mp[dist];
            }
            for (auto &item : mp)
                ans += item.second * (item.second - 1);
        }

        return ans;
    }
};