Leetcode相等行列对问题：我的代码超时，相似解法却通过？

问题原因分析 #

你的代码超时的核心原因在于HashMap的额外开销以及内存缓存效率问题，具体如下：

1. HashMap的访问开销
   你用HashMap<Integer, ArrayList<Integer>>存储行列数据，每次通过row.get(k)或col.get(l)获取列表时，需要执行哈希计算、桶查找等操作，相比直接用ArrayList<ArrayList<Integer>>的索引访问（O(1)直接内存偏移），额外开销显著。当n较大时（比如测试用例中的全1矩阵n=200），n²次get操作的累加开销会直接导致超时。

2. 内存缓存与GC压力
   你的代码一次性存储了2n个完整的ArrayList，占用大量堆内存，会降低CPU缓存命中率，同时增加垃圾回收（GC）的频率和开销。而通过的代码每次生成行列列表后立即比较，用完即被回收，内存占用更小，缓存效率更高。

3. 列生成的缓存未命中累积
   Java二维数组是行优先存储的，你的代码在预处理阶段集中进行跨列访问（grid[j][i]），会导致大量缓存未命中；而通过的代码将跨列访问分散在比较过程中，JVM的缓存机制更易处理这种分散式访问，性能损耗更小。

优化建议 #

方案1：替换HashMap为ArrayList存储行列

去掉HashMap的额外开销，直接用ArrayList存储行列列表，访问速度更快：

class Solution {
    public int equalPairs(int[][] grid) {
        ArrayList<ArrayList<Integer>> rows = new ArrayList<>(grid.length);
        ArrayList<ArrayList<Integer>> cols = new ArrayList<>(grid.length);
        int n = grid.length;

        // 存储所有行
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> row = new ArrayList<>(n);
            for (int j = 0; j < n; j++) {
                row.add(grid[i][j]);
            }
            rows.add(row);
        }

        // 存储所有列
        for (int j = 0; j < n; j++) {
            ArrayList<Integer> col = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                col.add(grid[i][j]);
            }
            cols.add(col);
        }

        int count = 0;
        for (ArrayList<Integer> row : rows) {
            for (ArrayList<Integer> col : cols) {
                if (row.equals(col)) count++;
            }
        }
        return count;
    }
}

方案2：哈希统计优化（时间复杂度O(n²)）

将行转换为唯一标识（如字符串或自定义哈希值），统计行的出现次数，再遍历列查找对应次数，彻底避免O(n³)的元素比较：

class Solution {
    public int equalPairs(int[][] grid) {
        Map<String, Integer> rowFreq = new HashMap<>();
        int n = grid.length;

        // 统计每行的出现频率
        for (int[] row : grid) {
            StringBuilder sb = new StringBuilder();
            for (int num : row) {
                sb.append(num).append(","); // 用分隔符避免数字拼接歧义（如1+11 vs 11+1）
            }
            String key = sb.toString();
            rowFreq.put(key, rowFreq.getOrDefault(key, 0) + 1);
        }

        int count = 0;
        // 遍历每列，累加对应行的频率
        for (int j = 0; j < n; j++) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(grid[i][j]).append(",");
            }
            String key = sb.toString();
            count += rowFreq.getOrDefault(key, 0);
        }

        return count;
    }
}

内容的提问来源于stack exchange，提问作者Kushagra Srivastava