447. 回旋镖的数量.md

447. 回旋镖的数量

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

思路

• 两层循环遍历
• 对于 points 中的每一个点，都计算它与 points 其他点的距离 dis，维护一个 map，key 是这个距离 dis 的值，value 为 points 中与该点符合该距离的点的数量（例如和点 pointA 相距 2 的点有 3 个，那么可能的组合就有3*2种方式， 即n*(n-1) ）
• 计算每一个点满足要求的所有组合，即遍历关于每个点的 map，计算出所有距离的个数的所有组合方式 count * (count - 1) 再相加

代码

/**
 *
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    let result = 0;
    for (let i = 0; i < points.length; i++) {
        // key是距离，value是符合该距离的点的数量
        let disCountMap = new Map();

        for (let j = 0; j < points.length; j++) {
            if (i !== j) {
                const dis = getDis(points[i], points[j]);
                if (disCountMap.has(dis)) {
                    disCountMap.set(dis, disCountMap.get(dis) + 1);
                } else {
                    disCountMap.set(dis, 1);
                }
            }
        }
       // 算出当前点符合的组合数
        for (let count of disCountMap.values()) {
            result += count * (count - 1);
        }
    }

    return result;
};

/**
 * 计算两点之间的距离
 */
var getDis = function(pointA, pointB) {
    const x = pointA[0] - pointB[0];
    const y = pointA[1] - pointB[1];
    return x ** 2 + y ** 2
}

复杂度

• 时间 O(n^2)
• 空间 O(n)