题目描述
给定平面上 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
