題目描述
給定平面上 n 對不同的點，“回旋鏢” 是由點表示的元組 (i, j, k) ，其中 i 和 j 之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序）翩隧。
找到所有回旋鏢的數(shù)量补憾。你可以假設(shè) n 最大為 500，所有點的坐標(biāo)在閉區(qū)間 [-10000, 10000] 中舌厨。
示例:
輸入:
[[0,0],[1,0],[2,0]]
輸出:
2
解釋:
兩個回旋鏢為 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
分析
遍歷，以當(dāng)前的節(jié)點為軸忿薇，使用map統(tǒng)計跟當(dāng)前節(jié)點距離一樣的數(shù)量裙椭。map的key是距離，value是數(shù)量
再遍歷統(tǒng)計的結(jié)果署浩，計算結(jié)果,計算的方式是:數(shù)量c, c * (c - 1)揉燃。表示c個節(jié)點中取任意兩個的排列數(shù)。
示例中：
跟1距離相等的個數(shù)是2,2*(2 - 1) = 2
代碼
class Solution {
public:
int getDis(pair<int,int> &a, pair<int, int> &b){
int x = b.first - a.first;
int y = b.second - a.second;
return x * x + y * y;
}
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int ans = 0;
for(int i = 0; i < points.size(); i++){
unordered_map<int,int> m; //統(tǒng)計與i同距離的個數(shù)
for(int j = 0; j < points.size(); j++){
if(i==j) {
continue;
}
int d = getDis(points[i], points[j]);
++m[d];
}
for(auto& it:m) {
if(it.second < 2) {
continue;
}
ans += it.second * (it.second - 1);
}
}
return ans;
}
};
題目鏈接
https://leetcode-cn.com/problems/number-of-boomerangs/description/
