447_回旋镖的数量

难度：中等

题目

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

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

示例

示例一：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例二：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例三：

输入：points = [[1,1]]
输出：0

提示

  • n == points.length
  • 1 <= n <= 500
  • points[i].length == 2
  • $-10^4<= x_i, y_i <= 10^4$
  • 所有点都 互不相同

解题

这道题的题目比较傻逼，讲的很迷糊

可以把回旋镖理解为一个V形结构，两边变长相同

回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等

所以可以对i进行枚举，找到一对和他距离相同的 j和k

对每个点，计算它与 i点的距离，然后以距离为键值通过哈希表存储点的数量

因为题目要求考虑元组的顺序，所以num个与i点距离相同的点可以构成num(num-1)个元组（若不考虑顺序，则num(num-1)/2）

为了简化计算，欧氏距离可以不用开平方，直接计算 $x^2+y^2$ 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int numberOfBoomerangs(int[][] points){
    int ans = 0;
    int n = points.length;
    for (int i=0; i<n;i++){
        Map<Integer,Integer> map = new HashMap<>();
        for (int j=0; j<n; j++){
            if (i==j){
                continue;
            }
            int x = points[i][0]-points[j][0];
            int y = points[i][1]-points[j][1];
            int dist = x*x + y*y;
            map.put(dist,map.getOrDefault(dist,0)+1);
        }
        for (int key: map.keySet()){
            int m = map.get(key);
            ans += m*(m-1);
        }
    }
    return ans;
}