给定平面上 n 互不相同 的点 points ,其中 points[i] = [xi, yi]回旋镖 是由点 (i, j, k) 表示的元组 ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。

返回平面上所有回旋镖的数量。

 

示例 1:

输入:points = [[0,0],[1,0],[2,0]]
输出:2
解释:两个回旋镖为 [[1,0],[0,0],[2,0]][[1,0],[2,0],[0,0]]

示例 2:

输入:points = [[1,1],[2,2],[3,3]]
输出:2

示例 3:

输入:points = [[1,1]]
输出:0

 

提示:

  • n == points.length
  • 1 <= n <= 500
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • 所有点都 互不相同
Related Topics
  • 数组
  • 哈希表
  • 数学

  • 👍 158
  • 👎 0
  • 9月13日 今天的每日一题

    就,摁解,遍历求解每一个点,和其他点距离相同的个数,比如有点的几个【P1,P2,P3,P4】,从P1开始,算出P1与所有点的距离情况,并统计出距离相同的情况个数。

    假设有3个连线的距离相等,这3条线为L1(P1,P2),L2(P1,P3),L3(P1,P4),则这三条线仍然有不同的组合可能,(L1,L2)、(L1、L3)、(L2、L4),已知公式两两组合的可能性个数为n*(n-1)/2,又因为题面中提出了有顺序不同,可以反向也算一种,那么就可以把底部的除2约掉

    则统计出有n条长度相同的线的话就可以得到 有n*(n-1)种可能组合

    代码

    class Solution {
        public int numberOfBoomerangs(int[][] points) {
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            final int[] count = {0};
            int[] point1,point2;
            for (int i = 0; i < points.length; i++) {
                point1 = points[i];
                hashMap.clear();
                for (int j = 0; j < points.length; j++) {
                    if (i==j)continue;
                    point2 = points[j];
                    int distance = (point1[0]-point2[0])*(point1[0]-point2[0]) + (point1[1]-point2[1])*(point1[1]-point2[1]);
                    hashMap.put(distance,hashMap.getOrDefault(distance,0)+1);
                }
                hashMap.forEach((key, value) -> {
                    if (value > 1) {
                        count[0] += value * (value - 1);
                    }
                });
            }
            return count[0];
        }
    }