题目

给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法：

• 添加 一个在数据流中的新点到某个数据结构中。可以添加 重复 的点，并会视作不同的点进行处理。
• 给你一个查询点，请你从数据结构中选出三个点，使这三个点和查询点一同构成一个 面积为正 的 轴对齐正方形 ，统计 满足该要求的方案数目。

轴对齐正方形 是一个正方形，除四条边长度相同外，还满足每条边都与 x-轴 或 y-轴 平行或垂直。

实现 DetectSquares 类：

• DetectSquares() 使用空数据结构初始化对象
• void add(int[] point) 向数据结构添加一个新的点 point = [x, y]
• int count(int[] point) 统计按上述方式与点 point = [x, y] 共同构造 轴对齐正方形 的方案数。

来源：力扣（LeetCode）

解答

两个解答点：

1. add方法

需要通过一个嵌套的哈希表来进行实现，保存了对应点的x, y 坐标及对应的点的数量（因为可能存在同坐标的重复点）。

2. count计算

因为要计算的是正方形，因此可以通过以下步骤完成计算：

1. 设给定点的坐标为(x, y)
2. 遍历与给定点同横坐标的点(x, yy)，来计算所构成正方形的边长（需注意横坐标相同，但纵坐标不能也相同，因为这样无法构成正方形）；
3. 每一个遍历的点(x, yy)，与给定点(x, y)横坐标相同，所以构成的长方形边长为length的同时，另外两个点一定是在这两个点的左侧，即坐标为(x-length, y) & (x-length, yy)，要么是在右侧，即坐标为(x+length, y) & (x+length, yy)。通过找这几个点，来确定同length边长下的正方形的数量即可。

代码如下：

class DetectSquares {
private:
    unordered_map<int, unordered_map<int, int>> all;

public:
    DetectSquares() {

    }

    void add(vector<int> point) {
        all[point[0]][point[1]]++;
    }

    int count(vector<int> point) {
        int x = point[0];
        int y = point[1];
        int ret = 0;

        // 遍历与给定点同列的点
        for (auto i: all[x]) {
            // 相同点，则pass，因为距离为0，无法构成正方形
            if (i.first == y) {
                continue;
            }

            int yy = i.first;            // 同列点的纵坐标
            int length = abs(yy - y); // 正方形边长

            // 因为有重复的点，i.second是遍历到某坐标后add点的个数
            ret += i.second * (all[x + length][yy] * all[x + length][y] +
                               all[x - length][yy] * all[x - length][y]);
        }

        return ret;
    }
};