> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/447-number-of-boomerangs.md).

# 447 Number of Boomerangs

## 447. [Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/description/)

## 1. Question

Givennpoints 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 thatnwill 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]]
```

## 2. Implementation

思路:\
(1) 对每个point A，我们都找出它和其他点所形成的距离

(2) 将这些距离存入一个hashmap中，key是距离的值，value是和point A构成这个距离值得点的个数

(3) 接下来如果point A对应的是boomerang的i, 那么我们接下来要求(j, k)的总排列. 遍历hashmap，对于每个key对应的value，根据排列公式 n!/ (n - 2)! = n(n - 1), 能形成boomberangs的个数等于 value \* (value - 1)

```
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                int distance = getDistance(points[i], points[j]);

                map.put(distance, map.getOrDefault(distance, 0) + 1);
            }

            for (Integer value : map.values()) {
                res += value * (value - 1);
            }
            map.clear();
        }
        return res;
    }

    public int getDistance(int[] p1, int[] p2) {
        int dx = p1[0] - p2[0];
        int dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
}
```

## 3. Time & Space Complexity

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