相等行列对 图解题解

这道题到底在问什么

输入

[[3,2,1],[1,7,6],[2,7,7]]

输出

1（第 2 行 [2,7,7] = 第 1 列 [2,7,7]）

输入

[[1,1],[1,1]]

输出

4（每行都等于每列）

最优解：一步一步想明白

1. 3记住「行存签名 → 逐列查表累加」。下面分两段：先哈希所有行，再扫所有列。
2. 4读第 0 行第 0 个数 3，把它接到这一行的签名后面，现在是 (3)。
3. 5读第 0 行第 1 个数 2，把它接到这一行的签名后面，现在是 (3,2)。
4. 6读第 0 行第 2 个数 1，把它接到这一行的签名后面，现在是 (3,2,1)。
5. 7第 0 行完整签名 (3,2,1) 存进哈希表、计 1。哈希只记「签名 → 出现几次」，不在乎它是第几行。
6. 8读第 1 行第 0 个数 1，把它接到这一行的签名后面，现在是 (1)。
7. 9读第 1 行第 1 个数 7，把它接到这一行的签名后面，现在是 (1,7)。
8. 10读第 1 行第 2 个数 6，把它接到这一行的签名后面，现在是 (1,7,6)。
9. 11第 1 行完整签名 (1,7,6) 存进哈希表、计 1。哈希只记「签名 → 出现几次」，不在乎它是第几行。
10. 12读第 2 行第 0 个数 2，把它接到这一行的签名后面，现在是 (2)。
11. 13读第 2 行第 1 个数 7，把它接到这一行的签名后面，现在是 (2,7)。
12. 14读第 2 行第 2 个数 7，把它接到这一行的签名后面，现在是 (2,7,7)。
13. 15第 2 行完整签名 (2,7,7) 存进哈希表、计 1。哈希只记「签名 → 出现几次」，不在乎它是第几行。
14. 16三行的签名都进了哈希表。接下来换个方向，竖着一列一列取出签名，到表里查有没有哪一行和它一模一样。
15. 17竖着取第 0 列第 0 个数 3，把列签名接起来，现在是 (3)。
16. 18竖着取第 0 列第 1 个数 1，把列签名接起来，现在是 (3,1)。
17. 19竖着取第 0 列第 2 个数 2，把列签名接起来，现在是 (3,1,2)。
18. 20第 0 列签名 (3,1,2) 在哈希表里没找到，没有哪一行和它完全相同，答案不变，仍是 0 对。
19. 21竖着取第 1 列第 0 个数 2，把列签名接起来，现在是 (2)。
20. 22竖着取第 1 列第 1 个数 7，把列签名接起来，现在是 (2,7)。
21. 23竖着取第 1 列第 2 个数 7，把列签名接起来，现在是 (2,7,7)。
22. 24第 1 列签名 (2,7,7) 在哈希表里命中 1 次（第 2 行和它一样）。答案加 1，现在共 1 对。绿色就是这对相等的行和列。
23. 25竖着取第 2 列第 0 个数 1，把列签名接起来，现在是 (1)。
24. 26竖着取第 2 列第 1 个数 6，把列签名接起来，现在是 (1,6)。
25. 27竖着取第 2 列第 2 个数 7，把列签名接起来，现在是 (1,6,7)。
26. 28第 2 列签名 (1,6,7) 在哈希表里没找到，没有哪一行和它完全相同，答案不变，仍是 1 对。
27. 29全部列扫完，一共 1 对相等的行列（第 2 行 = 第 1 列）。靠「行哈希 + 逐列查表」，只花 O(n²) 就避开了三重循环两两比对。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import Counter
class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        rows = Counter(tuple(row) for row in grid)
        n = len(grid)
        ans = 0
        for c in range(n):
            ans += rows[tuple(grid[r][c] for r in range(n))]
        return ans

#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        unordered_map<string, int> rows;
        auto key = [](const vector<int>& v) {
            string s;
            for (int x : v) { s += to_string(x); s += ','; }
            return s;
        };
        for (auto &row : grid) rows[key(row)]++;
        int n = grid.size(), ans = 0;
        for (int c = 0; c < n; ++c) {
            vector<int> col;
            col.reserve(n);
            for (int r = 0; r < n; ++r) col.push_back(grid[r][c]);
            ans += rows[key(col)];
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int equalPairs(int[][] grid) {
        Map<String, Integer> rows = new HashMap<>();
        for (int[] row : grid) {
            String key = Arrays.toString(row);
            rows.put(key, rows.getOrDefault(key, 0) + 1);
        }
        int n = grid.length, ans = 0;
        for (int c = 0; c < n; c++) {
            int[] col = new int[n];
            for (int r = 0; r < n; r++) col[r] = grid[r][c];
            ans += rows.getOrDefault(Arrays.toString(col), 0);
        }
        return ans;
    }
}

复杂度

面试官可能追问