21-05-30-回旋镖的数量

题目地址

https://leetcode-cn.com/problems/number-of-boomerangs/

题目描述

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

思路

两层遍历，算某个节点到其它所有节点的距离，利用哈希表存取距离，哈希表的键表示为距离，值为相同这个距离的个数。map = {距离: 该距离个数} 最后每层遍历完，count加上每种距离排列组合（因为题目节点的顺序也要算作不同）出来的个数。

代码

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
  const length = points.length;
  if (length <= 1) return 0;
  function calcDist([x1, y1], [x2, y2]) {
    return Math.pow(x1 - x2, 2) + Math.pow(y1- y2, 2);
  }

  let count = 0;

  for (let i = 0; i < length; i ++) {
    const map = new Map();
    for (let j = 0; j < length; j ++) {
      if (j !== i) {
        const dist = calcDist(points[i], points[j]);
        if (map.has(dist)) {
          map.set(dist, map.get(dist) + 1);
        } else {
          map.set(dist, 1);
        }
      }
    }
    map.forEach((value, key) => {
      count += value * (value - 1)
    });
  }
  return count;
};

复杂度分析

• 时间复杂度：O(N^2)
• 空间复杂度：O(N)