447. 回旋镖的数量#

题目#

1
给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。
2

3
回旋镖 是由点 (i, j, k) 表示的元组 ，
4

5
其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。
6

7
返回平面上所有回旋镖的数量。
8

9
示例 1：
10

11
输入：points = [[0,0],[1,0],[2,0]]
12
输出：2
13
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
14

15
示例 2：
16

17
输入：points = [[1,1],[2,2],[3,3]]
18
输出：2
19

20
示例 3：
21

22
输入：points = [[1,1]]
23
输出：0
24

25

26
提示：
27

28
n == points.length
29
1 <= n <= 500
30
points[i].length == 2
31
-10^4 <= xi, yi <= 10^4
32
所有点都 互不相同

题目思路#

本题翻译成人话就是：求二维平面上所给的点中，能组成等腰三角形两条腰边的三个顶点共有多少组，返回其总数；
使用 unordered_map 处理：在确定 i 作为三元组第一个点的回旋镖个数之前，先计算 i 与其余点的距离，以 {距离 : 个数} 的形式存储，最后分别对所有的距离进行累加计数。

题目代码#

代码块#

1
class Solution {
2
public:
3
    int numberOfBoomerangs(vector<vector<int>>& p) {
4
        int n = p.size();
5
        int ans = 0;
6
        for(int i = 0; i < n; i++)
7
        {
8
            unordered_map<int, int> up;
9
            for(int j = 0; j < n; j++)
10
            {
11
                if(i == j) continue;
12
                int x = p[i][0] - p[j][0];
13
                int y = p[i][1] - p[j][1];
14
                int d = x * x + y *y;
15
                ++up[d];
16
            }
17
            for(auto [d, cnt] : up)
18
            {
19
                ans += cnt * (cnt - 1);
20
            }
21
        }
22
        return ans;
23
    }
24
};

复杂度#

时间复杂度：O( $n^2$ )
空间复杂度：O( $n$ )