# LeetCode447. Number of Boomerangs（模拟）

## LeetCode447. Number of Boomerangs（模拟）

• Easy
• Accepted：50,055
• Submissions：102,203

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

### 链接

https://leetcode.com/problems/number-of-boomerangs/

### 题解

• 三重暴力循环找三个点，时间复杂度$O(n^3)​$
• 因为求的是i点到其余两点距离相等，所以我们可以把i点看做“中心点”，对于每一个点i，求其到其余点的距离，把距离和该距离出现的次数cnt建立键值对关系，放入查找表中，如果cnt大于1，那么对于该点的答案为$cnt * (cnt-1)$ ，最后再累加即可，时间复杂度为$O(n^2)​$

### 代码

• Runtime: 568 ms, faster than 72.22% of C++ online submissions for Number of Boomerangs.
• Memory Usage: 133.6 MB, less than 100.00% of C++ online submissions for Number of Boomerangs.
class Solution {
public:
int dis(pair<int, int> &pa, pair<int, int> pb) // 防止小数使用距离平方
{
return (pa.first - pb.first) * (pa.first - pb.first) +
(pa.second - pb.second) * (pa.second - pb.second);
}

int numberOfBoomerangs(vector<pair<int, int>>& points) {
int ans = 0;
for (int i = 0; i < points.size(); ++i)
{
unordered_map<int, int> umap;
for (int j = 0; j < points.size(); ++j)
if (j != i)
umap[dis(points[i], points[j])]++; // “距离相同的点”
for (auto it : umap)
{
if (it.second > 1)
ans += it.second * (it.second - 1);
}
}
return ans;
}
};

The end.
2019年2月17日 星期日