查看一个网站开发语言app下载推广

【LetMeFly】447.回旋镖的数量：哈希表

力扣题目链接：https://leetcode.cn/problems/number-of-boomerangs/

给定平面上 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
• 所有点都 互不相同

方法一：哈希表

第一重循环枚举每个$j$点。对于points[j]，使用一个哈希表，记录所有的点到j点的距离的出现次数。然后遍历哈希表，假设某距离出现了cnt次，那么就将$cnt\times (cnt-1)$累加到答案中。

• 时间复杂度$O(len(points{)}^2)$
• 空间复杂度$O(len(points))$

AC代码

C++

class Solution {
public:int numberOfBoomerangs(vector<vector<int>>& points) {int ans = 0;for (vector<int>& p : points) {unordered_map<int, int> ma;for (vector<int>& q : points) {ma[(p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])]++;}for (auto [_, cnt] : ma) {ans += cnt * (cnt - 1);}}return ans;}
};

Python

# from typing import List
# from collections import defaultdictclass Solution:def numberOfBoomerangs(self, points: List[List[int]]) -> int:ans = 0for p in points:ma = defaultdict(int)for q in points:ma[(p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])] += 1for _, cnt in ma.items():ans += cnt * (cnt - 1)return ans

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135464460