题目
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]]
难度
Easy
方法
对于每个point，用一个map统计各个距离d下对应的其他point的个数n，即map的key为距离d，value为距离该point为d的其他point的个数n。然后An取2，即n*(n-1)。最后将各个point对应的n*(n-1)累加即可
python代码
class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
result = 0
for point_i in points:
distance_map = {}
for point_j in points:
distance = (point_i[0] - point_j[0]) * (point_i[0] - point_j[0]) + \
(point_i[1] - point_j[1]) * (point_i[1] - point_j[1])
distance_map[distance] = distance_map.get(distance, 0) + 1
for distance in distance_map:
count = distance_map[distance]
result += count * (count - 1)
return result
assert Solution().numberOfBoomerangs([[0,0], [1,0], [2,0]]) == 2
