TLE for O(N^2/2)


  • 0
    S
    class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int n = points.size();
            vector<unordered_map<int, int>> distMap(n);
            int result = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j <n; j++) {
                    int diffx = points[j].first - points[i].first;
                    int diffy = points[j].second - points[i].second;
                    int sdistji = diffx*diffx + diffy*diffy;
                    result += 2 * distMap[i][sdistji];
                    distMap[i][sdistji]++;
                    result += 2 * distMap[j][sdistji];
                    distMap[j][sdistji]++;
                }
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.