LeetCode 2352. 相等行列对
目录
题目描述
题意分析
给一个
n x n的整数矩阵，要数出有多少个「行列对」(R_i, C_j)满足第i行和第j列作为序列完全相同。相同的定义是严格的：长度一样、对应位置的元素一一相等，顺序不能变 —— 不是集合相等，不是排序后相等。有三点必须先明确。第一，行和列都是长度为
n的序列，比较时行从左往右读、列从上往下读，这是唯一约定的读法。第二，统计的是有序对的数目，行取自行、列取自列，i和j之间没有任何限制 —— 第 0 行可以和第 2 列配成一对，第 0 行也可以同时和第 3 列再配一对。第三，如果多行内容相同、多列内容也相同，它们之间会两两配对，官方样例 2 里第 2 行和第 3 行内容都是[2,4,2,2]，各自与第 2 列配成一对，贡献了 2 个答案 —— 这说明本题不是找「配对关系」，而是老老实实做乘法计数。约束是
n <= 200、元素值域1 <= grid[i][j] <= 10^5。n只有 200 意味着行列各 200 条、每条 200 个元素，总数据量四万个整数，$O(n^3)$ 的两两暴力也只有八百万次比较，其实能过；但 $O(n^2)$ 的做法同样好写，没有理由退而求其次。值域上到 $10^5$ 是个隐藏提示：多位数的存在会让「把数字直接连起来」这种偷懒的序列表示法产生歧义，[11, 1]和[1, 11]会撞成同一个表示。边界：
n最小为 1，此时唯一的行和唯一的列都是同一个单元素序列，必然相等，答案是 1；矩阵中所有元素相同时，n行与n列两两全等，答案是n * n，这也是答案的上界。
解法：哈希表统计行签名 + 逐列匹配
核心思路
暴力做法是三重循环：枚举行
i、枚举列j、逐位比较n个元素，$O(n^3)$。瓶颈在于每一行都要和每一列各比一次，同一行的内容被反复读取了n遍；而这n遍读的是完全相同的数据，只是对手换了。关键观察是：判断两个序列相等，可以不做逐位比较，而是先把每个序列压成一个可以直接判等的签名，之后比较签名即可。既然行与行之间的比较毫无意义（我们只关心行列之间），那就把所有行的签名先统计进哈希表，再逐列生成签名去查表 —— 行只需要读一遍，列也只需要读一遍，$O(n^2)$。哈希表里存的是「签名 → 出现次数」，因为多行可能内容相同，查表得到的次数正是这一列能配出的对数，直接累加就完成了乘法计数，不需要任何嵌套。
签名的设计是本题真正的考点。它必须满足一个硬性要求：两个序列的签名相等，当且仅当两个序列逐位相等。把元素用一个分隔符连成字符串（如
3,1,2,2,）就满足这个要求，因为分隔符切出的每一段与原始元素一一对应。反过来，如果省掉分隔符直接拼接，[11, 1]和[1, 11]都会变成111，签名相等但序列不同，计数就会虚高 —— 本题值域到 $10^5$，多位数俯拾皆是，这个坑一定会踩到。同样地，在 Java 里直接把int[]当作哈希键也不行，数组的哈希与相等判断都基于引用而非内容，任何两个不同的数组对象都不相等，查表恒定落空。于是不变量可以写成：遍历到第
j列时，哈希表里恰好记录了全部n行的签名及其重数，累加值等于所有行与前j列构成的相等对数。行必须先全部统计完再开始查列，顺序不能交错，否则会漏掉那些「行号大于当前列号」的配对。生成列签名时可以复用同一个长度为
n的缓冲数组，每列覆写一遍即可，不必每列都新开数组 —— 签名一旦生成就是独立的字符串，缓冲区的后续改动影响不到它。
解题步骤
- 记
n = grid.length，准备一个「签名 → 出现次数」的哈希表。为什么：相同内容的行可能有多条，必须记重数才能做乘法计数；只记「见过没见过」会把样例 2 的答案从 3 少算成 2。- 遍历每一行，生成签名并把计数加一。为什么：行的签名只依赖行本身，一次遍历就能全部收集，之后无论多少列来查都不必重算。
- 定义签名函数：把序列里的元素依次追加到字符串构造器，每个元素后面都补一个分隔符。为什么：分隔符保证「签名相等」严格等价于「逐位相等」；末尾也补是为了让
[1]与[1, 1]这类前缀关系同样能被区分开。- 开一个长度为
n的缓冲数组，对每一列j，让i从0到n-1取出grid[i][j]填进缓冲区。为什么：列在内存里是纵向散落的，必须先收集成连续序列才能生成签名；复用同一个缓冲区可以避免n次数组分配。- 用列签名查哈希表，把查到的次数累加进答案（查不到按 0 算）。为什么：查到的次数就是与这一列内容相同的行的条数，每一条都能与当前列配成一对，累加即完成计数。
- 遍历完所有列后返回累加值。为什么：每个
(行, 列)有序对恰好在其所属列被处理时统计一次，不重不漏。以
grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]走一遍：n = 4，期望答案 3。先统计行签名：第 0 行
[3,1,2,2]→3,1,2,2,，计数 1；第 1 行[1,4,4,5]→1,4,4,5,，计数 1；第 2 行[2,4,2,2]→2,4,2,2,，计数 1；第 3 行内容相同，2,4,2,2,的计数升到 2。哈希表最终是三个键，其中一个重数为 2。再逐列查表。第 0 列纵向读出
[3,1,2,2]，签名3,1,2,2,，查到计数 1，答案累加到 1 —— 对应「第 0 行与第 0 列」这一对。第 1 列读出[1,4,4,4]，签名1,4,4,4,，表里没有，累加 0。第 2 列读出[2,4,2,2]，签名2,4,2,2,，查到计数 2，答案累加到 3 —— 这一步同时统计了「第 2 行与第 2 列」和「第 3 行与第 2 列」两对，正是重数派上用场的地方。第 3 列读出[2,5,2,2]，签名2,5,2,2,，表里没有，累加 0。最终返回 3，与期望一致。分隔符的必要性用
grid = [[11,1],[1,11]]验证：正确签名下，两行分别是11,1,与1,11,，两列分别是11,1,与1,11,，各配成一对，答案是 2。若省掉分隔符，四条序列的签名全是111，每列都查到计数 2，答案变成 4。
n = 1边界：grid = [[1]]，唯一的行签名1,计数 1，唯一的列签名也是1,，查到 1，返回 1，符合「唯一的行必然等于唯一的列」。
代码实现
class Solution {
public int equalPairs(int[][] grid) {
int n = grid.length;
// 键是行的签名，值是重数：内容相同的行可能有多条，必须计数而非去重。
Map<String, Integer> cnt = new HashMap<>();
for (int[] row : grid) {
cnt.merge(key(row), 1, Integer::sum);
}
int ans = 0;
// 复用同一个缓冲区收集列，签名生成后缓冲区可以随意覆写。
int[] col = new int[n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
col[i] = grid[i][j];
}
// 查到几条同内容的行，这一列就贡献几对。
ans += cnt.getOrDefault(key(col), 0);
}
return ans;
}
private String key(int[] a) {
StringBuilder sb = new StringBuilder();
for (int v : a) {
// 分隔符不可省：否则 [11,1] 与 [1,11] 会撞成同一个签名。
sb.append(v).append(',');
}
return sb.toString();
}
}
func equalPairs(grid [][]int) int {
n := len(grid)
// 键是行的签名，值是重数：内容相同的行可能有多条，必须计数而非去重。
cnt := map[string]int{}
for _, row := range grid {
cnt[key(row)]++
}
ans := 0
// 复用同一个缓冲区收集列，签名生成后缓冲区可以随意覆写。
col := make([]int, n)
for j := 0; j < n; j++ {
for i := 0; i < n; i++ {
col[i] = grid[i][j]
}
// 查到几条同内容的行，这一列就贡献几对。
ans += cnt[key(col)]
}
return ans
}
func key(a []int) string {
var sb strings.Builder
for _, v := range a {
// 分隔符不可省：否则 [11,1] 与 [1,11] 会撞成同一个签名。
sb.WriteString(strconv.Itoa(v))
sb.WriteByte(',')
}
return sb.String()
}
复杂度分析
- 时间复杂度：$O(n^2)$，统计行签名要读遍 $n$ 行共 $n^2$ 个元素，逐列收集与查表同样是 $n$ 列各 $n$ 个元素；签名长度与 $n$ 同阶，哈希与比较的开销也线性于签名长度，因此每条序列的处理是 $O(n)$，总量仍是 $O(n^2)$，相比暴力的 $O(n^3)$ 少掉一整层。
- 空间复杂度：$O(n^2)$，哈希表最坏要存 $n$ 条互不相同的行签名、每条长度 $O(n)$；缓冲数组只有 $O(n)$，不影响量级。若矩阵里行的种类很少，实际占用会远低于这个上界。
关键点总结
- 把「序列相等」换成「签名相等」，比较就能从 $O(n)$ 降到 $O(1)$。所有「多对多找相同」的题都适用这一招：先给每个对象算一个可哈希的签名，再用哈希表把两两比较拍平成一次查表。
- 签名必须是无歧义的。判断标准只有一条：签名相等能不能反推出对象相等。数字直接拼接会因为多位数产生歧义，必须加分隔符；同理，在 Java 里数组不能直接当哈希键，因为它的相等语义是引用而非内容。设计签名时先问一句「有没有两个不同对象撞到一起」。
- 要计数就得记重数，不能只记有无。本题一行可能与多列配对、一列也可能与多行配对，哈希表的值必须是出现次数，累加时直接加次数就完成了乘法计数，比嵌套两层循环去数干净得多。
- 先把一侧全部入表，再遍历另一侧查表。两边交错处理会漏掉一部分配对，这个「先建后查」的顺序是所有哈希配对题的固定节奏。
- 面试视角：这题最容易被追问的是「不用字符串还能怎么做签名」。可以答：用
List<Integer>作键（内容相等语义天然正确，但装箱开销大），或者对每条序列做一次滚动哈希把它压成一个 64 位整数（快，但要接受哈希碰撞的极小概率，或碰撞时回退到逐位比较）。另一个方向是「$n$ 只有 200，$O(n^3)$ 也能过，为什么还要优化」，答案是当 $n$ 放大到几千时暴力立刻失效，而签名法不受影响 —— 能同时说清「暴力为何能过」和「为何仍不该写」，比只会背最优解更有说服力。
易错点总结
- 签名不加分隔符，直接把数字拼起来：
[[11,1],[1,11]]→ 输出4，正确答案是2。四条序列全被压成111，每列都查到 2。官方给的两个样例元素都是一位数，完全测不出这个 bug，必须自己造多位数用例。- 直接把
int[]当哈希表的键：三个官方样例一律输出0。Java 数组的哈希码和相等判断都基于对象身份，两个内容相同的数组永远不相等，查表恒定落空。要用内容语义就得换成字符串、List<Integer>或自己算的哈希值。- 只统计下标相同的行列对（即只判断
grid[i][j] == grid[j][i]）：[[3,2,1],[1,7,6],[2,7,7]]→ 输出0，期望1；[[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]→ 输出2，期望3。这等于把题目误读成「判断矩阵是否对称」，行号与列号之间其实没有任何绑定关系。- 哈希表只记「出现过」不记次数：样例 2 → 输出
2而不是3，第 2 行和第 3 行内容相同、都该与第 2 列配对，去重后只算了一次。这条错误在没有重复行的数据上完全隐形，而官方样例 1 恰好没有重复行。- 把行和列的签名混在同一张哈希表里统计后再配对：会把「行与行相同」「列与列相同」也算进去，答案严重虚高。两侧必须分开：一侧建表、另一侧查表。
- 列的收集写成
col[i] = grid[j][i]，行列下标写反：实际收集的是第j行，于是变成拿行去和行比，[[3,2,1],[1,7,6],[2,7,7]]会输出3（每行与自己相等）。下标一反就成了另一道题，且样例仍能跑出数字、不会崩溃。- 每列新开一个数组却忘了清空复用的缓冲区：本题因为每次都把
n个位置全部覆写，复用是安全的；但如果改成「只在需要时写入」的写法，上一列的残留值就会混进签名。复用缓冲区的前提是每轮完整覆写，这个前提要显式确认。- 用
Arrays.toString生成签名：结果正确，但每条序列都要额外拼出方括号和空格，字符串更长、哈希更慢，且把实现细节绑死在库函数的输出格式上。自己拼分隔符更短也更可控。- 在统计行的同一层循环里就开始查列：哈希表尚未收齐全部行，前面的列查不到后面的行，会漏掉一批配对。必须两遍走完，先建表后查表。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 49. 字母异位词分组 | 中等 | 同样靠签名 + 哈希表分组，但签名要对内容排序以刻意抹掉顺序，与本题「顺序必须保留」正好相反 |
| 867. 转置矩阵 | 简单 | 只做行列互换不做统计，可以先转置再直接比对行与行，是理解「列如何变成序列」的最简形态 |
| 1512. 好数对的数目 | 简单 | 同为「哈希计数做乘法配对」，但配对发生在同一个数组内部，要处理组合数而非两侧独立计数 |
| 1207. 独一无二的出现次数 | 简单 | 两层哈希统计，考察的是对出现次数本身再做去重，与本题「重数参与累加」形成对照 |
| 1074. 元素和为目标值的子矩阵数量 | 困难 | 同样把二维问题压成一维序列后用哈希表匹配，只是压缩手段是前缀和而不是原样收集 |