447. Number of Boomerangs

Boomerangs回旋镖

1. Question

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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).

Return the number of boomerangs.

2. Examples

Example 1:

Input: points = [[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]].


Example 2:

Input: points = [[1,1],[2,2],[3,3]]
Output: 2


Example 3:

Input: points = [[1,1]]
Output: 0


3. Constraints

• n == points.length
• 1 <= n <= 500
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

5. Solutions

(i, j, k)中要求i与j的距离相等，且i与k的距离相等，但j和k的距离不一定相等。所以内层遍历结束后需要将hashmap置空。

class Solution {
public int numberOfBoomerangs(int[][] points) {
int ans = 0;
int n = points.length;
for (int i = 0; i < n; i++) {
HashMap<Integer, Integer> map = new HashMap();
for (int j = 0; j < n; j++) {
int a = points[i][0] - points[j][0];
int b = points[i][1] - points[j][1];
int dist = a * a + b * b;
Integer val = null;
if ((val = map.get(dist)) == null) {
map.put(dist, 1);
} else {
ans += val;
map.put(dist, val + 1);
}
}
}
return ans * 2;
}
}