> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/tong-ji-pin-lv/number-of-boomerangs.md).

# Number of Boomerangs

<https://leetcode.com/problems/number-of-boomerangs/description/>

> 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 rang&#x65;**\[-10000, 10000]**(inclusive).

## Thoughts

问题是要对于所有点，把和该点距离相同的按序抽出两个。因此我们可以对每个点统计下和它距离相同的点所形成的set， 对每个set抽俩。

## Code

```
class Solution {
    private int getDistance(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];

        return dx*dx + dy*dy;
    }

    public int numberOfBoomerangs(int[][] points) {
        Map[] maps = new Map[points.length];
        for (int i = 0; i < points.length; i++) {
            maps[i] = new HashMap<Integer, Integer>();
            Map<Integer, Integer> map = maps[i];
            for (int j = 0; j < points.length; j++) {
                if (j == i) {
                    continue;
                }
                int distance = getDistance(points[i], points[j]);
                if (!map.containsKey(distance)) {
                    map.put(distance, 1);
                } else {
                    map.put(distance, (int)map.get(distance) + 1);
                }
            }
        }

        int res = 0;
        for (Map<Integer, Integer> map : maps) {
            for (Integer dis : map.keySet()) {
                if (map.get(dis) > 1) {
                    res += map.get(dis) * (map.get(dis) - 1);
                }
            }
        }

        return res;
    }
}
```

## Analysis

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

## Ver.2

可以重复利用一个map.

```
class Solution {
    private int getDistance(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];

        return dx*dx + dy*dy;
    }

    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (j == i) {
                    continue;
                }
                int distance = getDistance(points[i], points[j]);
                if (!map.containsKey(distance)) {
                    map.put(distance, 1);
                } else {
                    map.put(distance, (int)map.get(distance) + 1);
                }
            }

            for (Integer dis : map.keySet()) {
                if (map.get(dis) > 1) {
                    res += map.get(dis) * (map.get(dis) - 1);
                }
            }
            map.clear();
        }

        return res;
    }
}
```