[LeetCode] 447. Number of Boomerangs

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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).

Return the number of boomerangs.

Example 1:

Input: points = [[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]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]]
Output: 2

Example 3:

Input: points = [[1,1]]
Output: 0

Constraints:

n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
All the points are unique.

回旋镖的数量。

给定平面上 n 对互不相同的点 points ，其中 points[i] = [xi, yi] 。回旋镖是由点 (i, j, k) 表示的元组，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-boomerangs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道数学题。注意回旋镖的定义，其实就是求二维坐标内是否存在三个不同的点，两两之间的距离相等。如果是暴力解，那么起码是 O(n^3) 级别的复杂度，因为需要枚举三个不同的点。这里为了降低复杂度，我们可以考虑，对于同一个点 i 来说，我们能找到多少 (j, k) 的组合，使得 j 和 k 分别到 i 的距离是相等的。计算坐标系内两点之间的距离的步骤其实不需要开根号，参见代码中 helper 函数。

所以这里我们需要一个两层 for 循环，第一层是遍历 i ，第二层是遍历其他所有的点，看看有多少个不同的距离 distance。最后统计的时候是 count * (count - 1)。

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public int numberOfBoomerangs(int[][] points) {
 3         int res = 0;
 4         for (int i = 0; i < points.length; i++) {
 5             HashMap<Integer, Integer> map = new HashMap<>();
 6             for (int j = 0; j < points.length; j++) {
 7                 if (i == j) {
 8                     continue;
 9                 }
10                 int dis = helper(points[i], points[j]);
11                 map.put(dis, map.getOrDefault(dis, 0) + 1);
12             }
13             for (int key : map.keySet()) {
14                 int c = map.get(key);
15                 res += c * (c - 1);
16             }
17         }
18         return res;
19     }
20 
21     private int helper(int[] point1, int[] point2) {
22         int x = point1[0] - point2[0];
23         int y = point1[1] - point2[1];
24         return x * x + y * y;
25     }
26 }