835. Image Overlap

这里的关键是如何把一个dy,dx hash成一个key
推倒过程如下

// To map a point in A to a point in B, we can use a vector [dy, dx] to represent the move
        // We can use dy * (2cols) + dy to hash this vector
        // (ay * 2cols + ax) - (by *2cols + bx) = (ay - by) * 2cols + (ax - bx) = dy * 2cols + dx
        // dx (-cols, cols) dy(-rows, rows)
        // so the hash factor should be (2 * cols - 1)
Time O(mn~m^2n^2)

59.20 %
class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int rows = A.length;
        int cols = A[0].length;
        int hash = 2 * cols - 1;
        List<Integer> listA = new ArrayList<>();
        List<Integer> listB = new ArrayList<>();
        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < cols; x++) {
                if (A[y][x] == 1) {
                    listA.add(y * hash + x);
                }
                if (B[y][x] == 1) {
                    listB.add(y * hash + x);
                }
            }
        }
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int a : listA) {
            for (int b : listB) {
                int diff = a - b;
                int count = 1 + map.getOrDefault(diff, 0);
                max = Math.max(max, count);
                map.put(diff, count);
            }
        }
        return max;
    }
}