[Leetcode C++解析] 447. Number of Boomerangs

大家好
這次要講的題目是Number of Boomerangs
題目網址 https://leetcode.com/problems/number-of-boomerangs/#/description

這一題小弟覺得不算是簡單的題目
(可能我數學不夠好XDD)
在此稍微說明一下題目：
給你一個包含n個tuple
(tuple的中文好像是數對，就是每一個tuple包含兩個數字x,y)
要在這n個tuple之中
找出符合像"boomerang"條件的組數量
也就是說從中抓任意三個點A.B.C
從A到B的距離"等於"從A到C的距離
其中(A,B,C)和(A,C,B)是不一樣的組合(考慮順序)

最多500個tuple
數值範圍介於-10000~10000

舉例來說

輸入：[[0,0],[1,0],[2,0],[0,1]]

符合boomerang的條件有
[1,0],[0,0],[2,0]
[2,0],[0,0],[1,0]
[0,0],[1,0],[0,1]
[0,0],[0,1],[1,0]
總共4種
因此輸出4

《以下是我的解題方式》
一開始我想了很久不知從何下手
用手算還算容易
後來一直盯著上面的結果看
就大致想到了
先任意抓出兩個點算長度
固定前面的點讓他去跟剩下的點算長度後做比較
有找到一樣的就把結果存起來

不過這樣有個問題是
時間複雜度會到O(n^3)
(最外面的一層是控制第一個點，中間那層控制第二個點，最裡面那層控制第三個點)
在別的相似題中會出現TLE的狀態

後來求助大神後
改成以下的作法

一樣先計算其中兩個點的長度
藉由unordered_map的container來做table
key：兩點的長度(平方)
value：有幾組tuple是這個長度

每算完一次兩點長度
就把這長度對應的那一欄+1
算完之後
由排列組合的概念：
對於每固定一個點之後
在剩下的點中距離這個點為___的個數是n
則表示能構成boomerange的種類有
P(n,2) =  n! / (n-2)! = n * (n-1)
再把答案加總即可

舉一個較簡單的例子

輸入：[[0,0],[1,0],[2,0],[0,1]]

以上面的例子來說
所有的可能性為
[0,0],[1,0] → 1
[0,0],[0,1] → 1
[0,0],[2,0] → 4
2! / 0! = 2

[1,0],[0,0] → 1
[1,0],[2,0] → 1
[1,0],[0,1] → 2
2! / 0! = 2

[2,0],[0,0] → 4
[2,0],[1,0] → 1
[2,0],[0,1] → 5
No~

[0,1],[0,0] → 1
[0,1],[1,0] → 2
[0,1],[2,0] → 5
No~

答案為2+2=4
《曾經錯過的測資》
無

《程式碼在這》
【小提醒：盡量自己先參考上面的想法寫出來，這樣比較不會有背程式碼的概念】


class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int ans=0;
     
        for(int i=0;i<points.size();++i){
            unordered_map<long,int> res;
            for(int j=0;j<points.size();++j){
                if(i==j) continue;//
             
                int x = points[i].first - points[j].first;
                int y = points[i].second - points[j].second;
                long distance = x*x + y*y;
             
                ++res[distance];
            }
         
            for(auto& ptr : res){
                if(ptr.second>1){
                    ans += (ptr.second * (ptr.second -1));
                }
            }
         
        }
     
        return ans;
    }
};