做网站的软件公司/青岛网站制作设计

题目

OJ平台

题目解析

基本思路：

1. 任意两个点的距离，用二维数组存储。

2. 根据每次外层循环选中的序号构建关于该序号的回旋镖，用哈希表存储到达该点的距离次数。注意每轮重新清空哈希表。

3. 根据An2求出每轮的答案相加即可。

可用于把第一步优化掉，直接用两层循环记录任意两点的距离，哈希表直接存值即可。

代码实现

我的实现–二维数组+哈希表+An2

class Solution {
public:int numberOfBoomerangs(vector<vector<int>>& points) {int ans=0,size=points.size(),dist[size][size];memset(dist,0,sizeof(dist));unordered_map<int, int> check;for (int i = 0; i < size; ++i){//j=i+1避免重复计算for (int j = i+1; j < size; ++j){int dx = points[i][0] - points[j][0];int dy = points[i][1] - points[j][1];dist[i][j] = dist[j][i] = dx*dx + dy*dy;}for (int k = 0; k < size; ++k){++check[dist[i][k]];//统计到i距离相同的点}for (auto c : check){//A2排列数ans += c.second * (c.second-1);}check.clear();}return ans;
}
};

官方实现–哈希表+An2

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