LeetCode 750. 角矩形的数量
目录
题目描述
题意分析
给一个只含 $0$ 和 $1$ 的矩阵
grid，要求统计其中「角矩形」的个数。角矩形的定义是：取四个格子，它们的值都是 $1$，并且这四个格子恰好构成一个轴对齐矩形的四个角——也就是说它们分布在两条不同的行和两条不同的列的交点上。矩形内部和边上的其他格子是什么值完全不管。定义本身给出了最强的信号：一个角矩形被「两行 + 两列」这四条线唯一确定，而不是被四个坐标独立确定。这意味着问题的自由度只有两维（选哪两行、选哪两列），而不是四维，直接把朴素的四重枚举压到二重枚举加计数。
第二个信号是值域只有 $0$ 和 $1$。这让「某一列在某两行上是否都为 $1$」变成一个纯布尔判断，可以用简单的相乘或与运算表达，也为后续用位运算加速留了空间。
约束方面：行数
m和列数n都在 $1$ 到 $200$ 之间，矩阵里 $1$ 的总数不超过 $6000$，答案保证在 $32$ 位整数范围内。$m^2 n$ 大约是 $200^2 \times 200 = 8 \times 10^6$，完全可以接受；而四重枚举是 $m^2 n^2$ 约 $1.6 \times 10^9$，会超时。这组数字正是在暗示「按行对枚举」这条路。边界上要覆盖：只有一行或只有一列（凑不出两条不同的行/列，答案必为 $0$）；某两行的公共 $1$ 列数为 $0$ 或 $1$（此时组合数为 $0$，不能贡献负数）；整张矩阵全是 $1$（答案是行对数乘列对数，用来验算公式）；矩阵中 $1$ 极其稀疏。
解法：枚举行对 + 组合计数
核心思路
最直白的暴力是四重循环：枚举上边行
r1、下边行r2、左列c1、右列c2，检查四个交点是否都是 $1$。复杂度 $O(m^2 n^2)$，在 $200 \times 200$ 的规模下约 $1.6 \times 10^9$ 次判断，必然超时。瓶颈在于：内层的两重列枚举做了大量重复劳动。固定
r1和r2之后，判断「列c上这两行是否都为 $1$」这件事对每一列是独立的，而四重循环把每一列的这个判断重复做了 $O(n)$ 遍（因为它对每个(c1, c2)组合都要重新检查两端）。关键观察：固定两行之后，问题退化成一个纯计数问题。设这两行中「同一列上都是 $1$」的列有
common条，那么任取其中两条列，都必然能和这两行围出一个合法的角矩形；反之任何以这两行为上下边的角矩形，它的左右两列也必然都属于这common条。所以这对行的贡献恰好是从common条列里选两条的组合数 $\binom{common}{2} = \frac{common \times (common - 1)}{2}$，一次算式代替了内层的 $O(n^2)$ 枚举。于是维护的量非常简单：对每一对行 $(r_1, r_2)$（要求 $r_1 < r_2$），
common表示满足grid[r1][c] == 1 && grid[r2][c] == 1的列数；答案是所有行对的 $\binom{common}{2}$ 之和。这里不需要 dp 数组，common只是一个在每对行内部从零开始重新累加的局部计数器。为什么每个角矩形不会被重数或漏数？因为枚举时强制 $r_1 < r_2$，所以「上下两行」的选法与无序行对一一对应；而组合数 $\binom{common}{2}$ 本身就是无序地选两列。两者相乘，每个角矩形恰好在它自己那对行、那对列上被数一次，既不重也不漏。
至于要不要枚举列对而不是行对——两者对称，选行数较小的那一维做外层平方可以省常数，但在 $m, n \le 200$ 的规模下没有必要，保持代码简单更重要。
解题步骤
取出
m = grid.length、n = grid[0].length，答案累加器answer初始化为 $0$。理由：n只需读一次，放在循环外避免重复取长度；题目保证矩阵非空，所以grid[0]可以安全访问。外层
for (int r1 = 0; r1 < m; r1++)，内层for (int r2 = r1 + 1; r2 < m; r2++)。理由：r2从r1 + 1开始，一次性保证了两行不同且不会把 $(a, b)$ 和 $(b, a)$ 数两遍；如果写成r2 = 0再判r1 != r2，答案会正好翻倍。在每对行的开头把
common重置为 $0$。理由：common的语义是「当前这对行的公共 $1$ 列数」，它必须随行对更换而重新统计；忘记重置会让计数一路累积，答案偏大到离谱。最内层遍历所有列
c，当grid[r1][c] == 1 && grid[r2][c] == 1时common++。理由：两个条件必须同时成立才说明这一列能同时给上下两行提供角点；用&&短路还能在上行为 $0$ 时省掉一次访问。列循环结束后执行
answer += common * (common - 1) / 2。理由：这一步把 $O(n^2)$ 的列对枚举替换成常数时间的组合公式；common为 $0$ 或 $1$ 时该式自然得 $0$，不需要额外判断。先乘后除的顺序不能颠倒：必须写
common * (common - 1) / 2而不是common / 2 * (common - 1)。理由：common与common - 1中必有一个是偶数，所以乘积一定能被 $2$ 整除；但先除会在common为奇数时因整数截断丢掉 $0.5$，结果偏小。全部行对遍历完后返回
answer。理由：每个角矩形只在其唯一的行对上被计入一次，累加完即为总数。以
grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]走一遍（$m = 4$，$n = 5$）。行对 $(0,1)$：逐列比较，列 $0$ 是1/0、列 $1$ 是0/0、列 $2$ 是0/1、列 $3$ 是1/0、列 $4$ 是0/1，没有一列两行同时为 $1$，common = 0，贡献 $0$。行对 $(0,2)$：列 $3$ 上是1/1，其余不匹配，common = 1，贡献 $\frac{1 \times 0}{2} = 0$——只有一条公共列时凑不出矩形，公式自动给 $0$。行对 $(0,3)$：列 $0$ 上是1/1，列 $3$ 上是1/0，common = 1，贡献 $0$。行对 $(1,2)$：列 $2$ 是1/0，列 $4$ 是1/0，列 $3$ 是0/1，common = 0，贡献 $0$。行对 $(1,3)$：列 $2$ 上是1/1，列 $4$ 上是1/1，common = 2，贡献 $\frac{2 \times 1}{2} = 1$——这就是由第 $1$、$3$ 行与第 $2$、$4$ 列围成的那个角矩形。行对 $(2,3)$：列 $3$ 是1/0，common = 0，贡献 $0$。总计answer = 1，与期望一致。
代码实现
class Solution {
public int countCornerRectangles(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int answer = 0;
for (int r1 = 0; r1 < m; r1++) {
for (int r2 = r1 + 1; r2 < m; r2++) {
int common = 0;
for (int c = 0; c < n; c++) {
if (grid[r1][c] == 1 && grid[r2][c] == 1) {
common++;
}
}
answer += common * (common - 1) / 2;
}
}
return answer;
}
}
func countCornerRectangles(grid [][]int) int {
m := len(grid)
n := len(grid[0])
answer := 0
for r1 := 0; r1 < m; r1++ {
for r2 := r1 + 1; r2 < m; r2++ {
common := 0
for c := 0; c < n; c++ {
if grid[r1][c] == 1 && grid[r2][c] == 1 {
common++
}
}
answer += common * (common - 1) / 2
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(m^2 n)$，其中 $m$、$n$ 是矩阵的行数与列数。外两层枚举行对共 $\frac{m(m-1)}{2}$ 次，每次扫一遍所有列做 $O(n)$ 的比较，组合数计算是常数时间。相比四重枚举的 $O(m^2 n^2)$，把内层列对枚举换成一次公式，正好省掉一个 $n$。
- 空间复杂度：$O(1)$。除了
common和answer两个整型变量外没有任何辅助结构，输入矩阵是只读的、不做拷贝也不做预处理表。
关键点总结
- 几何计数题的第一步是找出决定一个图形的最小自由度。角矩形看似要定四个点，实际只要定两行两列，识别出这一点就把 $O(m^2n^2)$ 直接降到 $O(m^2n)$。同样的思路适用于「数平行四边形」「数轴对齐正方形」等题。
- 「枚举一部分维度 + 对剩余维度用组合公式」是降维计数的通用模板：固定住让问题变简单的那几维，剩下的如果彼此互不约束，就能用 $\binom{k}{2}$ 之类的闭式代替枚举。判断依据是「任取两个都合法」，本题的
common条列正好满足。- 枚举无序对时用
j = i + 1起手，而不是全枚举再去重。这既避免了重复计数，也省掉一次相等判断，是竞赛与面试里都通用的写法。- 整数运算中 $\binom{k}{2}$ 要写成
k * (k - 1) / 2，先乘后除。理由是相邻两数必有一偶，乘积必然整除 $2$；先除会截断出错。- 面试视角：拼多多、网易考这题的目的是看能不能主动做复杂度降维。标准答题节奏是先说出四重枚举的 $O(m^2n^2)$ 并指出会超时，再说「固定两行后左右两列的选择互不干扰，可以用组合数一次算完」，最后写十行代码。如果被追问还能不能更快，可以答：把每一行压成一个 $200$ 位的位图（
long[4]），行对的公共列数就是两个位图按位与之后的popcount，常数能降到约 $\frac{1}{64}$；或者反过来枚举列对并借助哈希表统计，在 $1$ 很稀疏时更优——本题限制 $1$ 的总数不超过 $6000$，正是给这条稀疏优化留的口子。
易错点总结
- 错误写法：内层循环写成
for (int r2 = 0; r2 < m; r2++)再用if (r1 == r2) continue;过滤 → 用例[[1,1],[1,1]]→ 行对 $(0,1)$ 与 $(1,0)$ 各算一次，答案变成 $2$，正确答案是 $1$。- 错误写法：把
common声明在两层行循环之外，只初始化一次 → 用例[[1,1],[1,1],[1,1]]→ 第二对、第三对行的计数在前面的基础上继续累加，common一路涨到 $6$，答案变成 $1 + 3 + 15 = 19$，正确答案是 $3$。- 错误写法：组合数写成
common / 2 * (common - 1)先除后乘 → 用例 某对行的common = 3→ 正确贡献是 $3$，但先除得 $1$ 再乘 $2$ 得 $2$，整数截断导致少算。- 错误写法：组合数写成
common * common / 2或common * (common + 1) / 2→ 用例common = 2→ 前者得 $2$、后者得 $3$，正确答案是 $1$；选两列是 $\binom{k}{2}$ 不是 $\binom{k+1}{2}$，也不含自己配自己。- 错误写法：公共列判断写成
grid[r1][c] == grid[r2][c]→ 用例[[0,0],[0,0]]→ 两行在两列上都相等（都是 $0$），common = 2，贡献 $1$，但一个 $1$ 都没有，正确答案是 $0$；必须要求两者都等于 1。- 错误写法：公共列判断写成
grid[r1][c] + grid[r2][c] >= 1（误用「或」的语义）→ 用例[[1,0],[0,1]]→ 两列都满足，common = 2，答案算成 $1$，正确答案是 $0$。- 错误写法：没有对
common < 2的情况做保护却把公式写成了减法形式如common * common - common之后再除 → 用例common = 0→ 结果虽仍是 $0$，但若误写成(common - 1) * (common - 2) / 2之类的偏移公式，common = 0时会得到 $1$，凭空多出一个不存在的矩形。- 错误写法：把
n写成grid.length而不是grid[0].length→ 用例 非方阵如 $2$ 行 $5$ 列的矩阵 → 列循环只跑 $2$ 次，右侧三列的 $1$ 全被忽略，答案偏小；若矩阵是 $5$ 行 $2$ 列则直接数组越界。- 错误写法：直接照搬四重枚举
for r1, for r2, for c1, for c2判断四点 → 用例 $200 \times 200$ 且 $1$ 较密集的矩阵 → 约 $1.6 \times 10^9$ 次判断，远超时限。- 错误写法：以为「角矩形要求内部或边上其他格子也是 1」而在统计时额外校验 → 用例
[[1,0,1],[0,0,0],[1,0,1]]→ 四个角都是 $1$ 但中间是 $0$，被错误排除，答案为 $0$，正确答案是 $1$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1074. 元素和为目标值的子矩阵数量 | 困难 | 同样枚举一对边界再把剩余维度压成一维，但用前缀和加哈希表而非组合公式 |
| 1277. 统计全为 1 的正方形子矩阵 | 中等 | 要求整块全为 $1$ 而非只看四角，靠动态规划递推边长而不是枚举行对 |
| 1139. 最大的以 1 为边界的正方形 | 中等 | 只要求四条边全为 $1$，需预处理行列方向的连续长度前缀 |
| 221. 最大正方形 | 中等 | 求最大面积而非计数，状态定义为「以该点为右下角的最大边长」 |
| 85. 最大矩形 | 困难 | 按行压缩成柱状图后用单调栈求最大面积，是矩阵问题降维的另一条主线 |