# 447. Number of Boomerangs 回旋镖的数量

@TOC

[LeetCode]

• Difficulty: Easy

## # 题目描述

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:

``````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]]
``````

## # 解题方法

``````public class Solution {
public int numberOfBoomerangs(int[][] points) {
int res = 0;
HashMap<Integer, Integer> hashmap=new HashMap<>();
for(int i =0; i< points.length; i++){
for(int j=0; j< points.length; j++){
if(i == j){
continue;
}
int distance = getDistance(points[i], points[j]);
hashmap.put(distance, hashmap.getOrDefault(distance, 0) + 1);

}
for(int val : hashmap.values()) {
res += val * (val-1);
}
hashmap.clear();
}
return res;
}
public int getDistance(int[] point1, int[] point2){
int dx= point2[0] - point1[0];
int dy=point2[1] - point1[1];
return dx*dx + dy*dy;
}
}
``````

AC: 188 ms 超过61%

python写法：

``````class Solution:
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
res = 0
for p0 in points:
d = collections.defaultdict(int)
for p1 in points:
d[(p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2] += 1
for d, v in d.items():
res += v * (v - 1)
return res
``````

## # 日期

2017 年 1 月 12 日 2018 年 11 月 14 日 —— 很严重的雾霾