LeetCode 447. Number of Boomerangs
撰写于 20180122 修改于 20180122 分类 LeetCode
Question
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).
Solution
At the first sight, I thought this problem is a math problem, to get all the vectors which is perpendicular to the other vector. Intuitively, it is a nice solution, however, it is very time consuming. So, here using hashMap is a better solution because you won’t get TLE
.
 For each point
p
, calculating the distance ofp
with other points and store the distance and its corresponding counts in a map.  For each point
p
, after getting the map, if the value of count is greater than 1, that means there are at least 2 points which can make a pair withp
. Since if there are 3 points which can make a pair withp
, the result is3 * 2
, that is permutation.
Code
Python


CPP

