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.length1 <= n <= 500points[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 }
相关题目