public static int numberOfBoomerangs(int[][] points) {
if (points.length < 2) {
return 0;
}
int sum = 0;
Map<Integer, Integer> lengthMap = new HashMap<>();
for (int i = 0; i < points.length; i++) {
lengthMap.clear();
for (int j = 0; j < points.length; j++) {
if (i == j) {
continue;
}
int length = (int) (Math.pow(points[j][0] - points[i][0], 2) + Math.pow(points[j][1] - points[i][1], 2));
if (lengthMap.containsKey(length)) {
lengthMap.put(length, lengthMap.get(length) + 1);
} else {
lengthMap.put(length, 1);
}
}
for(Integer length : lengthMap.keySet()) {
int subLen = lengthMap.get(length);
if (subLen > 1) {
sum += (subLen * (subLen - 1));
}
}
}
return sum;
}
解题思路
- 假设给你等边三角形的三个点，固定一个点再选两个点组成回旋镖 C(2,2)，有序再乘以2，三个点再乘以3，总结对应一个点既：
1）对于一个点 A，有N个点和A距离相等，那么能组成的回旋镖数为：C(2,N) * 2 = N*(N-2);
2）循环遍历各个点，找出相同长度的个数，这里用map存储各长度及其对应的个数；
3）遍历map计算每个长度能组成的回旋镖个数。
