題目描述

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

找到所有回旋鏢的數(shù)量。你可以假設(shè) n 最大為 500，所有點(diǎn)的坐標(biāo)在閉區(qū)間 [-10000, 10000] 中。

示例:

    輸入:
    [[0,0],[1,0],[2,0]]
    
    輸出:
    2
    
    解釋:
    兩個(gè)回旋鏢為 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

分析

遍歷，以當(dāng)前的節(jié)點(diǎn)為軸，使用map統(tǒng)計(jì)跟當(dāng)前節(jié)點(diǎn)距離一樣的數(shù)量。map的key是距離，value是數(shù)量
再遍歷統(tǒng)計(jì)的結(jié)果，計(jì)算結(jié)果,計(jì)算的方式是:數(shù)量c, c * (c - 1)。表示c個(gè)節(jié)點(diǎn)中取任意兩個(gè)的排列數(shù)。
示例中：
跟1距離相等的個(gè)數(shù)是2,2*(2 - 1) = 2

代碼

class Solution {
public:
    int getDis(pair<int,int> &a, pair<int, int> &b){
        int x = b.first - a.first;
        int y = b.second - a.second;
        return x * x + y * y;
    }
    
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int ans = 0;
        for(int i = 0; i < points.size(); i++){
            unordered_map<int,int> m; //統(tǒng)計(jì)與i同距離的個(gè)數(shù)
            for(int j = 0; j < points.size(); j++){
                if(i==j) {
                    continue;
                }
                int d = getDis(points[i], points[j]);
                ++m[d];
            }
            for(auto& it:m) {
                if(it.second < 2) {
                    continue;
                }
                ans += it.second * (it.second - 1);
            }
        }
        return ans;
    }
};

題目鏈接

https://leetcode-cn.com/problems/number-of-boomerangs/description/