【基础篇 - Day 21】 447. 回旋镖的数量

题目描述

入选理由

1. hashtable 用于数学抽象 + 数据统计

题目描述

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

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

我的回答

解法一

时空复杂度

时间复杂度：O(n^2)

空间复杂度: O(n)

var numberOfBoomerangs = function (points) {
    let result = 0
    for (let i = 0; i < points.length; i++) {
        let map = new Map()
        for (let j = 0; j < points.length; j++) {
            if (i === j) continue
            const length = Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2)
            const curr = map.get(length)
            if (curr) {
                map.set(length, curr + 1)
                result += (curr * 2)
            } else {
                map.set(length, 1)
            }
        }
    }
    return result
};

参考回答

• 官方题解