Number of Boomerangs

发表于 | 分类于

Number of Boomerangs

题目描述：

给定一组表示二维坐标的数组，要求找到所有的三元组(i,j,k)；其中i到j和i到k的距离相同。

例子：

具体描述见LeetCode447

解题思路：

首先我们定义外循环找到第一个点i,在此基础之上我们循环剩下的所有节点,用哈希表记录下剩下节点到i节点的距离的长度和对应的次数；而后对应节点i的循环结束之后我们找到哈希表中出现超过1次的距离，并根据公式将对应的可能加入到结果中即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int res = 0;
        
        for (int i = 0; i < points.size(); i++){
            unordered_map<int, int> hash;
            
            for (int j = 0; j < points.size(); j++){
                if (j == i) continue;
                int dy = points[j].second - points[i].second;
                int dx = points[j].first - points[i].first;
                
                int key = dx * dx;
                key += dy * dy;
                hash[key]++;
            }
            for (auto k : hash){
                if (k.second > 1){
                    res += k.second * (k.second - 1);
                }
            }
        }
        return res;
        
    }
};