# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/google/447-number-of-boomerangs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.