LeetCode|LeetCode 447. Number of Boomerangs 回旋镖个数时间复杂度O(n2) LeetCode447.NumberofBoomerangs回旋镖

解题思路

因为[i,j,k]三元组中i的位置是唯一的，所以我们可以固定i位对数组points进行遍历。
由高中学的排列组合的知识我们得到，以points[i]为i点、距离为l的boomerang的个数等于x*（x-1）（也就是A（x,2）），其中x为与points[i]的距离等于l的点的个数。
我们只要把这些x*（x-1）都加起来就能得到题目的答案

步骤

遍历数组points，将每个元素points[i]设置为[i,j,k]中的i点
再次遍历数组points，计算从points[i]到其余点的距离的平方（因为距离的平方与距离是一一对应的关系，这里使用距离的平方以节省计算时间），将这些距离的平方储存在列表list_distance中
使用计数器cnt计算list_distance中每个数字出现的次数x
将x*（x-1）累计入num_boomerang

【LeetCode|LeetCode 447. Number of Boomerangs 回旋镖个数时间复杂度O(n2)】原题链接
欢迎在我的博客轻松探索更多思路
代码

class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int:from collections import Counterif len(points)==1: return 0num_boomerang=0for i in range(len(points)): list_distance=[] for j in range(len(points)): if j==i: continue else: list_distance.append(pow(points[i][0]-points[j][0],2)+pow(points[i][1]-points[j][1],2))cnt=Counter(list_distance) for k in cnt: if cnt[k]>1: num_boomerang+=cnt[k]*(cnt[k]-1)return int(num_boomerang)