447. Number of Boomerangs -E !!!!!!!!!!!!!!!

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

A:

------------------------------记录每个距离的index pair, 然后再一起统计总数-------------
-------------就是O（n^2) 的复杂度，可是还是LTE  了。  不爽

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size();
        unordered_map<long,vector<vector<int>>> M;
        for(int i=0;i< n;++i)
        {
            for(int j = i+1; j<n;j++)
            {
                auto A = points[i];
                auto B = points[j];
                long dist = (A[0] - B[0]) * (A[0] - B[0]) + (A[1] - B[1]) * (A[1] - B[1]);
                if(M.find(dist) == M.end())
                {     
                    M.insert({dist, vector<vector<int>>() });
                }                    
                auto it = M.find(dist);
                it->second.push_back(vector<int>{i, j});
                it->second.push_back(vector<int>{j, i});
            }
        }
        // now count paris for each distance
        int res = 0;
        for(auto it = M.begin(); it != M.end(); ++it)
        {
            auto L = it->second;
            for(int i = 0;i<L.size();++i)
            {
                for(int j = i+1; j<L.size();++j)
                {
                    if(L[i][0] == L[j][0])
                        res++;
                }
            }
        }
        return 2*res;        
    }
};

--------------优化---------------------
考虑到都是i--> j   ==== i--> k    所以，我们可以边计算距离，边计数，这样就不保存了。
而且，针对每一个， i,j

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int res = 0;
        for(int i=0;i< points.size();++i)
        {
            unordered_map<long,vector<int> > M;
            auto A = points[i];
            for(int j = 0; j< points.size();j++)
            {                
                if(j==i)
                    continue;
                auto B = points[j];
                long dist = (A[0] - B[0]) * (A[0] - B[0]) + (A[1] - B[1]) * (A[1] - B[1]);
                if(M.find(dist) == M.end())
                {     
                    M.insert({dist, vector<int>() });
                }
                auto it = M.find(dist);
                it->second.push_back(j);
            }
            for(auto& it : M)
                res += it.second.size() * (it.second.size() -1);
        }
        return res;        
    }
};

如果想更省时间和空间，那么 map 里不存每个位置，考虑到我们只需要其size(). 因此我们只需要计数即可

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int res = 0;
        for(int i=0;i< points.size();++i)
        {
            unordered_map<long,int > M;
            auto A = points[i];
            for(int j = 0; j< points.size();j++)
            {                
                if(j==i)
                    continue;
                auto B = points[j];
                long dist = (A[0] - B[0]) * (A[0] - B[0]) + (A[1] - B[1]) * (A[1] - B[1]);
                if(M.find(dist) == M.end())
                {
                    M.insert({dist, 1 });
                }else{
                    auto it = M.find(dist);
                    it->second ++;
                }
            }
            for(auto& it : M)
                res += it.second * (it.second -1); // Combination (x, 2)
        }
        return res;        
    }
};

--------------------- 继续优化-------unordered_map<int,int> 允许直接 [  ] access，如果没有值的话，就默认为second value 的默认值。 对int， 就是0 

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int res = 0;
        for(int i=0;i< points.size();++i)
        {
            unordered_map<long,int > M;
            auto& A = points[i];
            for(int j = 0; j< points.size();j++)
            {                
                if(j==i)
                    continue;
                auto& B = points[j];
                long dist = (A[0] - B[0]) * (A[0] - B[0]) + (A[1] - B[1]) * (A[1] - B[1]);
                ++ M[dist];
            }
            for(auto& it : M)
                res += it.second * (it.second -1);
        }
        return res;        
    }
};