447. 回旋镖的数量

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

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

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2
示例 3：

输入：points = [[1,1]]
输出：0

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

image.png

根据题意，回旋镖是指，坐标上有三个点 i, j, k，i 到 j 的距离等于 i 到 k 的距离。上图中，蓝色的点到两个橙色的点距离是一样的，所以 (i, j, k) 构成了一个回旋镖，然后其实 (i, k, j) 也构成了一个回旋镖。

其实可以想到，对于每个点，我们只需要将其他点按照距离分组记录，比如上图中的 [1, 1]，跟它距离 2的平方根 的点有 [0, 0] 和 [2, 0]。然后再计算排列组合数，也就是对 2的平方根 这个距离的分组中的点进行两两排列组合，就可以得出答案了。

如果用哈希表来存，它的结构大概是这样的：

{
point1: {
dist1: [point2, point3],
dist2: [point4]
},
point2: {},
}
每个点都维护一个哈希表，哈希表的键是这个点到其他点的距离，值就是在这个距离的点有哪些。

不过题目只要求输出回旋镖的数量，所以我们只需要记录在某个距离的点有几个，并不需要记录具体的坐标，比如 dist1: 2 就可以了。

计算两点距离公式：

image.png

不过其实我们只关心距离是否一样，并不关心实际距离是多少，所以实际上不需要开根号。

  //时间复杂度O(n^2)
    //空间复杂度O(n)
    public int numberOfBoomerangs(int[][] points) {

        int res = 0;
        for (int i = 0; i < points.length; i++) {


            //record 中存储点 i 到所有其他点的距离出现的频次  大于1 说明距离相等，才是我们需要的
            HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
            for (int j = 0; j < points.length; j++)
                if (j != i) {
                    // 计算距离时不进行开根运算, 以保证精度
                    int dis = dis(points[i], points[j]);
                    if (record.containsKey(dis))
                        record.put(dis, record.get(dis) + 1);
                    else
                        record.put(dis, 1);
                }

            // 等于1 的会 被减一变为零 然后  xxx*0=0
            for (Integer dis : record.keySet())
                res += record.get(dis) * (record.get(dis) - 1);
        }

        return res;
    }

    private int dis(int[] pa, int pb[]) {
        return (pa[0] - pb[0]) * (pa[0] - pb[0]) +
                (pa[1] - pb[1]) * (pa[1] - pb[1]);
    }