Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

1
2
3
4
5
6
7
8
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

直接的做法:

  1. 针对每一个点, 计算其与其他点的距离, 存放在HashMap里, key 为距离, value 为点的数量
  2. 现在我们有了很多 pair. 根据排列的计算公式, 距离当前点为distance的两个点的排列的数量为 counter * (counter - 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
public int numberOfBoomerangs(int[][] points) {
    int count = 0;
    for (int i = 0; i < points.length; i++) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < points.length; j++) {
            if (j == i)
                continue;
            int dis = getDis(points[i], points[j]);
            if (!map.containsKey(dis)) {
                map.put(dis, 0);
            }
            map.put(dis, map.get(dis) + 1);
        }
        for (int v : map.values()) {
            count += v * (v - 1);
        }
    }
    return count;
}
private int getDis(int[] x, int[] y) {
    int dx = x[0] - y[0];
    int dy = x[1] - y[1];
    return dx * dx + dy * dy;
}