力扣447. 回旋镖的数量

力扣447. 回旋镖的数量

题目解析及思路

题目要求找到一个三元组(i,j,k)，其中**d(i,j) = d(j,k)**

外层枚举j，内层枚举i，同时计算d(i,j)，用哈希表储存，如果表中之前有存过相等的d

则res += 2 * cnt[d]，因为(i,j,k) 和 (k,j,i)算不同的三元组

代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        unordered_map<int,int> cnt;
        //枚举外层
        for(auto& p1 : points)
        {
            cnt.clear();
            for(auto& p2 : points)
            {
                //计算d(i,j)
                int d2 = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
                //先计算答案再存入哈希表
                ans += cnt[d2] * 2;
                cnt[d2] ++;
            }
        }
        return ans;
    }
};

原文地址：https://blog.csdn.net/Pisasama/article/details/142829957

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！