2352. 相等行列对

冷静思考的能力是一切智慧的开始，是一切善良的源泉。

LC每日一题，参考2352. 相等行列对。

题目

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。

如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。

输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
输出：3
解释：存在三对相等行列对：
- (第 0 行，第 0 列)：[3,1,2,2]
- (第 2 行, 第 2 列)：[2,4,2,2]
- (第 3 行, 第 2 列)：[2,4,2,2]

解题思路

• 哈希表+滚动哈希：使用哈希表对行列计数,使用滚动哈希用来比较。

哈希表+滚动哈希

class Solution {
    public int equalPairs(int[][] grid) {
        //先考虑暴力枚举
        int ans = 0,n = grid.length;
        //哈希统计 + 滚动哈希
        int P = 13;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int row = 0;
            for(int j = 0; j < n; j++) {
                row = row * P + grid[i][j];
            }
            map.put(row,map.getOrDefault(row,0)+1);
        }
        for(int i = 0; i < n; i++) {
            int col = 0;
            for(int j = 0; j < n; j++) {
                col = col * P + grid[j][i];
            }
            ans += map.getOrDefault(col,0);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，双重循环,n为矩阵行数/列数。
• 空间复杂度：O(n)，哈希表空间不超过n。