题目

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

找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入:
[[0,0],[1,0],[2,0]]

输出:
2

解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

思路

见代码注释

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        
        int res = 0;
        //存储 点i 到所有其他点的距离（key），和各个距离出现的频次（value）
        HashMap<Integer, Integer> map = new HashMap<>();

        //先将i看做第一个枢纽点，计算i和剩余其他点的距离
        //构成回旋镖需要至少有两个点和i的距离相等
        for(int i = 0; i < points.length; i++){

            for(int j = 0 ; j < points.length ; j++ ){
                if(i!=j){
                    //计算两点之间距离
                    int distance = distanceOfTwoPoints(points[i],points[j]);
                    // map中存储 点i 到所有其他点的距离出现的频次
                    map.put(distance,map.getOrDefault(distance, 0)+1);
                    /*if(!map.containsKey(distance))
                        map.put(distance, 1);
                    else
                        map.put(distance, map.get(distance)+1);*/
                }   
            }
            //计算i作为第一个枢纽点能构成的回旋镖的个数
            //第二个点的取值可能有num种，第三个点的取值可能有num-1种
            //如果num=0，说明没有相同的距离，num-1正好为0
            for(int num : map.values())
                res = res + num*(num-1);
            
            //清除map，为计算下一个点做准备
            map.clear();
        }

        return res;
        
    }
    public int distanceOfTwoPoints(int[] p1,int[] p2){
        //不开根号，保留距离的精度
        return (p1[0]-p2[0])*(p1[0]-p2[0])+(p1[1]-p2[1])*(p1[1]-p2[1]);
        
    }
}