2013.检测正方形

链接：2013.检测正方形
难度：Medium
标签：设计、数组、哈希表、计数
简介：给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法：添加 一个在数据流中的新点到某个数据结构中。可以添加 重复 的点，并会视作不同的点进行处理。给你一个查询点，请你从数据结构中选出三个点，使这三个点和查询点一同构成一个 面积为正 的 轴对齐正方形 ，统计 满足该要求的方案数目。

题解 1 - cpp

• 编辑时间：2022-01-26
• 执行用时：228ms
• 内存消耗：91.7MB
• 编程语言：cpp
• 解法介绍：统计每个点出现的次数。

class DetectSquares {
   public:
    unordered_map<int, unordered_map<int, int>> m;
    DetectSquares() {}
    void add(vector<int> point) { m[point[0]][point[1]]++; }
    int count(vector<int> point) {
        int ans = 0, x1 = point[0], y1 = point[1];
        for (auto &data : m[x1]) {
            int x2 = x1, y2 = data.first, cnt2 = data.second,
                edge = abs(y1 - y2);
            if (y2 == y1) continue;
            ans += cnt2 * m[x1 - edge][y1] * m[x2 - edge][y2];
            ans += cnt2 * m[x1 + edge][y1] * m[x2 + edge][y2];
        }
        return ans;
    }
};