回旋镖的数量
给定平面上 n 对 互不相同 的点 points ,其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ,其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等(需要考虑元组的顺序)。
返回平面上所有回旋镖的数量。
示例 1:
输入:points = [[0,0],[1,0],[2,0]]
输出:2
解释:两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
1
2
3
2
3
/**
* @param {number[][]} points
* @return {number}
*/
var numberOfBoomerangs = function(points) {
// 肯定组成不了回旋镖
if (points.length < 3) return 0;
const map = {};
let res = 0;
points.forEach((a, i) => {
// 遍历时,将每个点作为顶点
map[a] = {};
// 再次遍历,得到其余的点到顶点的距离
points.forEach((b, j) => {
// 排除与自身的点
if (i !== j) {
// 计算距离
const d = getD(a, b);
// 将距离保存
map[a][d] = (map[a][d] || 0) + 1;
}
});
// 遍历顶点map
for (const item in map[a]) {
// 与顶点相同距离的点的个数
const num = map[a][item];
// num>1,才能和顶点组成回旋镖
// 一共num,其中挑2个出来,有num*(num-1)个可能
if (num > 1) res += num * (num - 1);
}
});
return res;
};
// 计算两点距离的平方
var getD = ([a1, a2], [b1, b2]) => (b1 - a1) ** 2 + (b2 - a2) ** 2;
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
28
29
30
31
32
33
34
35
36
37
38
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
28
29
30
31
32
33
34
35
36
37
38
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/number-of-boomerangs