447.回旋镖的数量

链接：447.回旋镖的数量
难度：Medium
标签：数组、哈希表、数学
简介：返回平面上所有回旋镖的数量。

题解 1 - typescript

• 编辑时间：2021-09-13
• 执行用时：252ms
• 内存消耗：60.9MB
• 编程语言：typescript
• 解法介绍：map 储存。

function numberOfBoomerangs(points: number[][]): number {
  const n = points.length;
  const getDistance = ([x1, y1]: number[], [x2, y2]: number[]) => (x1 - x2) ** 2 + (y1 - y2) ** 2;
  const pointMap: Map<number[], Map<number, number>> = new Map();
  let ans = 0;
  for (let i = 0; i < n; i++) {
    const p1 = points[i];
    let map1 = pointMap.get(p1);
    if (!map1) pointMap.set(p1, (map1 = new Map()));
    for (let j = i + 1; j < n; j++) {
      const p2 = points[j];
      let map2 = pointMap.get(p2);
      if (!map2) pointMap.set(p2, (map2 = new Map()));
      const distance = getDistance(p1, p2);
      const count1 = map1.get(distance) ?? 0;
      map1.set(distance, count1 + 1);
      ans += count1 * 2;
      const count2 = map2.get(distance) ?? 0;
      map2.set(distance, count2 + 1);
      ans += count2 * 2;
    }
  }
  return ans;
}

题解 2 - python

• 编辑时间：2024-01-08
• 执行用时：788ms
• 内存消耗：17.06MB
• 编程语言：python
• 解法介绍：以一个点为中点，遍历所有其他点判断次数。

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p1 in points:
            map = Counter()n
            for p2 in points:
                d = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
                ans += map[d] * 2
                map[d] += 1
        return ans