[LeetCode]Number Of Corner Rectangles

题目链接

Brute Force的做法就是考虑每一个点作为右下节点的情况下，有多少个矩形，然后计算总和。时间复杂度O(m^2 * n^2)，m和n分别为输入矩阵的高度和长度。
稍微优化的做法就是枚举所有的两行，我们知道只有当这两行同一个列都为1的时候，这两个1才可能成为两个顶点。我们统计所有在这两行上，处在相同列上并且均为1的列数k。每一组1都是可能的两个顶点，每一组两两之间都可以构成corner rectangle，并且数量为k * (k - 1) / 2。时间复杂度O(m^2 * n)，代码如下：