447. 回旋鏢的數量

給定平面上 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

解題思路

枚舉+哈希表

對于每個點，我們計算出它與其他點的距離。對于到該點距離相同的點，我們加入到該距離對應的list中，該list中的任意兩個點都可以與該點形成回旋鏢，通過排列組合，我們可以計算出可以形成的回旋鏢的個數

代碼

class Solution {public int numberOfBoomerangs(int[][] points) {int n=points.length;Map<Integer,List<Integer>>[] map=new HashMap[n];for(int i=0;i<n;i++)map[i]=new HashMap<>();for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int x1=points[i][0],y1=points[i][1],x2=points[j][0],y2=points[j][1];int d=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);if(!map[i].containsKey(d))map[i].put(d,new ArrayList<>());if(!map[j].containsKey(d))map[j].put(d,new ArrayList<>());map[i].get(d).add(j);map[j].get(d).add(i);}int res=0;for(int i=0;i<n;i++){for(List l:map[i].values()){if(l.size()>=2)res+=l.size()*(l.size()-1);}}return res;} }

總結

以上是生活随笔為你收集整理的447. 回旋镖的数量的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。