LeetCode 2352. 相等行列对

约 5 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 LeetCode 75
标签
数组 哈希表 矩阵 模拟

题目描述

✅ 2352. 相等行列对

image-20260928234521613

image-20260928234521614

题意分析

对方阵的每个行下标 i 和列下标 j，把第 i 行从左到右的值，与第 j 列从上到下的值逐项比较。所有对应位置都相同，才构成一对，求这样的下标对总数。

序列顺序必须相同，不是元素集合或总和相同。内容相同但下标不同的行、列仍各自参与计数，因此不能简单去重后统计相等序列的种类数。

解法：行序列编码计数，再逐列查询

核心思路

[!blue]

直接比较每一行与每一列，需要对 n² 对序列分别检查 n 项。可以先将每条行序列编码为一个可作为哈希键的字符串，统计有多少行具有相同内容，再对每一列查询一次。

编码按原顺序追加每个整数的十进制表示，并在每项后加分隔符。分隔符明确划开整数边界，避免不同长度数值连在一起产生相同文本。行与列使用同一个编码函数，得到相同键恰好对应逐项相等。

cnt[key] 是这种序列的行数，而不是是否出现。每一列查到多少条相同行，就贡献多少个行列下标对；多列具有相同内容时，每列也各查一次，自然得到行重数与列重数的全部组合，不会漏计。

读取列时固定列号、让行号从小到大变化。可重复使用同一个整数缓冲数组，因为编码已经生成独立字符串，下一列覆盖缓冲内容不会改变保存的行键或本次查询。

解题步骤

  1. 逐行使用统一编码函数生成字符串键，在哈希表中累加行频次。
  2. 对每个列号，按行号递增顺序将整列读入缓冲数组。
  3. 对缓冲使用同样的编码，查询相同内容的行数并加入答案。
  4. 处理全部列后返回总下标对数。

代码实现

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();
    }
}

import (
    "strconv"
    "strings"
)

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 的序列，字符串构造与哈希总字符量同为平方级。
  • 空间复杂度：$O(n^2)$，最多保存 n 个长度为 $O(n)$ 的行签名，列缓冲另占 $O(n)$。

关键点总结

[!green]

  • 序列编码保留元素顺序，并用分隔符保留数值边界。
  • 哈希表保存重数，一列匹配多行时要累加全部行数。
  • 每个列下标独立查询，重复列也各自产生对应下标对。
  • 列缓冲可以复用，已经生成的字符串键不依赖缓冲后续内容。

易错点总结

[!yellow]

  • 编码时省略分隔符，不同整数边界可能拼成完全相同的字符串。
  • 用集合替代计数表，内容相同的多条行只保留一次，丢失不同下标对。
  • 将行列内部排序后再比较，接受了仅元素相同但原顺序不同的序列。
  • 从下到上读取列，却从左到右读取行，改变了题目规定的比较方向。
  • 只比较行和列的元素总和，和相同远不足以保证每项相同。

相似题目

题目 难度 关联与区别
867. 转置矩阵 简单 同样按列读取矩阵，转置后列变成行可帮助理解本题的序列比较。
49. 字母异位词分组 中等 同样把对象映射到规范签名再分组，本题必须保留原序列顺序，不能像异位词那样排序元素。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/93373575
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！