title

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input: [[0,0],[1,0],[2,0]] Output: 2

Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Analyze

思路:

首先弄清题意, 输入的数组 points 中能产生中多少种 [i, j, k] 的数组, 使 i 到 j 的距离与 i 到 k 的距离相等。

因此可以将 i 的位置固定, 使用查找表将到 i 的距离作为 key, 将该距离出现的次数作为 value, 若该次数大于 1 则说明能构成回旋镖。(比如出现 4 次, 在剩下的 j, k 两个位置中能构成 4 * 3 个回旋镖)

/**
* @param {number[][]} points
* @return {number}
*/
var numberOfBoomerangs = function (points) {
// avoid losing the precision
const getDistancePow = (x, y) => {
return Math.pow((y[0] - x[0]), 2) + Math.pow((y[1] - x[1]), 2)
}
let result = 0
for (let p = 0; p < points.length; p++) {
const tmpMap = new Map()
for (let n = 0; n < points.length; n++) {
if (p === n) continue
const distancePow = getDistancePow(points[p], points[n])
const hasDistancePow = tmpMap.has(`${distancePow}`)
if (hasDistancePow) {
tmpMap.set(`${distancePow}`, tmpMap.get(`${distancePow}`) + 1)
} else {
tmpMap.set(`${distancePow}`, 1)
}
}
tmpMap.forEach((value, key) => {
if (value > 1) {
const sum = value * (value - 1)
result += sum
}
})
}
return result
}

Similar Title

149