题目描述

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

刚拿到此问题完全没有头绪不知道该如何解答，参考了很多有智慧的前辈的方法后，总结出此题的解法。

首先如果我们用暴力方法求解，依次循环所有的元素，时间复杂度为O(n^3)这是一个不能接受的复杂度，接下来给出我的思路：

447.PNG

图中可以清晰的看出，我们可以将与point i 这一点的距离和点的个数存储到一个字典中，字典中的key为距离，而value为个数
现在问题基本迎刃而解，因为距离10的元素有1个，这并不符合我们的要求，我们需要的value大于等于2，也就是元素至少为2
下面是该题的python解法

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        res = 0
        # 距离查找表
        order_map = dict()
        #遍历第一次
        for i in range(len(points)):
            order_map.clear()
            #遍历第二次
            for j in range(len(points)):
                if j != i:
                    dist = self.__dis(points[i],points[j])
                    if dist not in order_map:
                        order_map[dist] = 1
                    else:
                        order_map[dist] += 1
            for key,value in order_map.items():
                if value >= 2:
                    res += value * (value-1)
        return res
    #这里开根号也许会丢失精度，不开根号是一样的
    def __dis(self,pa,pb):
        return (pa[0]-pb[0])*(pa[0]-pb[0])+(pa[1]-pb[1])*(pa[1]-pb[1])

447.PNG