【LetMeFly】447.回旋鏢的數(shù)量：哈希表

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

給定平面上?n 對(duì) 互不相同 的點(diǎn)?points ，其中 points[i] = [xi, yi] 。回旋鏢 是由點(diǎn)?(i, j, k) 表示的元組 ，其中?i?和?j?之間的距離和?i?和?k?之間的歐式距離相等（需要考慮元組的順序）。

返回平面上所有回旋鏢的數(shù)量。

?

示例 1：

輸入：points = [[0,0],[1,0],[2,0]]
輸出：2
解釋：兩個(gè)回旋鏢為 [[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
• 所有點(diǎn)都 互不相同

方法一：哈希表

第一重循環(huán)枚舉每個(gè)$j$點(diǎn)。對(duì)于points[j]，使用一個(gè)哈希表，記錄所有的點(diǎn)到j(luò)點(diǎn)的距離的出現(xiàn)次數(shù)。然后遍歷哈希表，假設(shè)某距離出現(xiàn)了cnt次，那么就將$cnt\times (cnt?1)$累加到答案中。

• 時(shí)間復(fù)雜度$O(len(points{)}^2)$
• 空間復(fù)雜度$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

同步發(fā)文于CSDN，原創(chuàng)不易，轉(zhuǎn)載經(jīng)作者同意后請(qǐng)附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135464460