题目

给定平面上 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

提示：

n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
所有点都互不相同
通过次数42,350提交次数64,704

题解

/*
 * 时间: 2021-09-13 21:47
 * 分析: 求满足给定条件的点
 * 思路:
 *  1. 遍历所有节点即可, 判断两点间的距离: (x1-x1)^2 + (y1 - y2)^2 (超时)
 * 优化:
 *  1. 在 思路1 的基础上优化性能, 先算出所有线之间的距离
 *  2. 在 优化1 的基础上修复错误, 将 HashMap<Integer, HashSet<Integer>> 修改为 HashMap<Integer, HashMap<Integer, Integer>>, 解决统计不准问题
 *  3. 在 优化2 的基础上修复错误, 修复计算总数问题
 */
class Solution0447_1 {
    public int numberOfBoomerangs(int[][] points) {
        int count = 0;
        HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            map.put(i, new HashMap<>());
        }

        for (int i = 0; i < points.length; i++) {
            HashMap<Integer, Integer> mapI = map.get(i);
            for (int j = i + 1; j < points.length; j++) {
                int len = (int)Math.pow(Math.abs(points[i][0] - points[j][0]), 2)
                        + (int)Math.pow(Math.abs(points[i][1] - points[j][1]), 2);

                HashMap<Integer, Integer> mapJ = map.get(j);
                count += 2 * mapI.getOrDefault(len, 0);
                count += 2 * mapJ.getOrDefault(len, 0);

                mapI.put(len, mapI.getOrDefault(len, 0) + 1);
                mapJ.put(len, mapJ.getOrDefault(len, 0) + 1);
            }
        }
        return count;
    }
}

Q.E.D.