LeetCode 835中等数组 · 哈希

图像重叠图解题解

这道题到底在问什么

给定两个 n×n 的二进制矩阵 img1 与 img2。允许把一张图里所有的 1 整体向上下左右平移任意距离(越界的 1 被清除,不能旋转),叠到另一张上。求两图同一位置都为 1 的最大数目。

输入: img1=[[1,1,0],[0,1,0],[0,1,0]], img2=[[0,0,0],[0,1,1],[0,0,1]]
输出: 3 （img1 向右 1、向下 1 后,有 3 个位置重叠）
输入: img1=[[1]], img2=[[1]]
输出: 1

先想最直接的笨办法

核心一句话:枚举两图所有 1 的配对,统计相对位移,计数最多的位移就是答案。下面每帧都在套它。（动画第 3 步）

最优解：一步一步想明白

3核心一句话:枚举两图所有 1 的配对,统计相对位移,计数最多的位移就是答案。下面每帧都在套它。
4绿色 = 1，蓝色 = 0，中间一列是分隔左半边是 img1,右半边是 img2,中间那列只作分隔。绿色格子是 1,蓝色是 0。我们要找一个平移,让两图的 1 尽量对上。
5img1 有 4 个 1先看 img1,它的 1 在 (0,0)、(0,1)、(1,1)、(2,1) 这 4 个位置,紫色圈出来。
6img2 有 3 个 1img2 的 1 在 (1,1)、(1,2)、(2,2) 这 3 个位置,橙色标出来。4 个 1 配 3 个 1,一共 12 对要枚举。
7第 1 个 img1 的 1轮到 img1 在 (0,0) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
8位移 [-1,-1]img1 的 (0,0) 对 img2 的 (1,1):位移 = (0-1, 0-1) = [-1,-1]。该位移计数变成 1。目前最高,[-1,-1] 暂列第一。
9位移 [-1,-2]img1 的 (0,0) 对 img2 的 (1,2):位移 = (0-1, 0-2) = [-1,-2]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
10位移 [-2,-2]img1 的 (0,0) 对 img2 的 (2,2):位移 = (0-2, 0-2) = [-2,-2]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
11第 2 个 img1 的 1轮到 img1 在 (0,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
12位移 [-1,0]img1 的 (0,1) 对 img2 的 (1,1):位移 = (0-1, 1-1) = [-1,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
13位移 [-1,-1]img1 的 (0,1) 对 img2 的 (1,2):位移 = (0-1, 1-2) = [-1,-1]。该位移计数变成 2。目前最高,[-1,-1] 暂列第一。
14位移 [-2,-1]img1 的 (0,1) 对 img2 的 (2,2):位移 = (0-2, 1-2) = [-2,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
15第 3 个 img1 的 1轮到 img1 在 (1,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
16位移 [0,0]img1 的 (1,1) 对 img2 的 (1,1):位移 = (1-1, 1-1) = [0,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
17位移 [0,-1]img1 的 (1,1) 对 img2 的 (1,2):位移 = (1-1, 1-2) = [0,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
18位移 [-1,-1]img1 的 (1,1) 对 img2 的 (2,2):位移 = (1-2, 1-2) = [-1,-1]。该位移计数变成 3。目前最高,[-1,-1] 暂列第一。
19第 4 个 img1 的 1轮到 img1 在 (2,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
20位移 [1,0]img1 的 (2,1) 对 img2 的 (1,1):位移 = (2-1, 1-1) = [1,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 3。
21位移 [1,-1]img1 的 (2,1) 对 img2 的 (1,2):位移 = (2-1, 1-2) = [1,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 3。
22位移 [0,-1]img1 的 (2,1) 对 img2 的 (2,2):位移 = (2-2, 1-2) = [0,-1]。该位移计数变成 2。当前最高仍是位移 [-1,-1],计数 3。
23最高位移 [-1,-1] 命中 3 次12 对全部枚举完。面板里 9 种不同位移,[-1,-1] 出现 3 次最多,其余位移都只 1 到 2 次。答案就锁在这个 3。
24这几对就是最终重叠点把贡献位移键 [-1,-1] 的 3 对 1 同时点亮:(0,0)↔(1,1)、(0,1)↔(1,2)、(1,1)↔(2,2)。注意这个键是 img1 坐标减 img2 坐标,实际移动 img1 去对齐要取相反方向,所以 [-1,-1] 对应 img1 实际向右 1、向下 1(移动哪张图只差一个相反号,计数不受影响)。这样平移后,正好这 3 个位置和 img2 重合。
25最大重叠 = 3所有位移里命中次数的最大值就是最大重叠数,这里是 3。最终答案:3。

⚠️ 容易写错的地方

✗ 错：真的去平移矩阵、还手动处理越界清零

✓ 对：不平移,只记 1 配对的相对位移并计数

越界的 1 自然配不出同一个位移,无需特判清零,代码大幅简化

✗ 错：位移方向一会儿 i-h 一会儿 h-i

✓ 对：全程固定 img1 坐标减 img2 坐标

方向混用会把同一平移拆成两个位移,计数被打散,答案偏小

✗ 错：两图无可配对 1 时对空计数取 max 报错

✓ 对：计数表为空直接返回 0

max 作用在空集合上会异常,要先判空

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

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        cnt = Counter()
        for i in range(n):
            for j in range(n):
                if img1[i][j]:
                    for h in range(n):
                        for k in range(n):
                            if img2[h][k]:
                                cnt[(i - h, j - k)] += 1
        return max(cnt.values()) if cnt else 0

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size();
        map<pair<int, int>, int> cnt;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j]) {
                    for (int h = 0; h < n; ++h) {
                        for (int k = 0; k < n; ++k) {
                            if (img2[h][k]) {
                                ans = max(ans, ++cnt[{i - h, j - k}]);
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        Map<List<Integer>, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j] == 1) {
                    for (int h = 0; h < n; ++h) {
                        for (int k = 0; k < n; ++k) {
                            if (img2[h][k] == 1) {
                                List<Integer> t = Arrays.asList(i - h, j - k);
                                ans = Math.max(ans, cnt.merge(t, 1, Integer::sum));
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
}

复杂度

时间

O(n⁴)

最坏整图都是 1,img1 的 1 与 img2 的 1 两两配对,约 n² × n² 对

空间

O(n²)

计数表里不同位移的个数,上界约 (2n-1)²

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着图像重叠的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

只枚举 1 还是 O(n⁴),能更快吗?+

理论上可以。把两图看成多项式,重叠数等价于一种二维卷积,用 FFT 可降到约 O(n² log n)。但面试里把「枚举 1 配对 + 位移计数」讲清通常就够,FFT 是加分项。

为什么用位移计数比真平移再逐位比较好?+

真平移要枚举 (2n-1)² 个位移,每个再花 O(n²) 比对,还要处理越界清零,同样是 O(n⁴) 但常数和代码都更重。位移计数只对 1 配对、不碰 0,代码短、常数小。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把图像重叠一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 835中等数组 · 哈希

图像重叠图解题解

这道题到底在问什么

输入: img1=[[1,1,0],[0,1,0],[0,1,0]], img2=[[0,0,0],[0,1,1],[0,0,1]]
输出: 3 （img1 向右 1、向下 1 后,有 3 个位置重叠）
输入: img1=[[1]], img2=[[1]]
输出: 1

先想最直接的笨办法

核心一句话:枚举两图所有 1 的配对,统计相对位移,计数最多的位移就是答案。下面每帧都在套它。（动画第 3 步）

最优解：一步一步想明白

3核心一句话:枚举两图所有 1 的配对,统计相对位移,计数最多的位移就是答案。下面每帧都在套它。
4绿色 = 1，蓝色 = 0，中间一列是分隔左半边是 img1,右半边是 img2,中间那列只作分隔。绿色格子是 1,蓝色是 0。我们要找一个平移,让两图的 1 尽量对上。
5img1 有 4 个 1先看 img1,它的 1 在 (0,0)、(0,1)、(1,1)、(2,1) 这 4 个位置,紫色圈出来。
6img2 有 3 个 1img2 的 1 在 (1,1)、(1,2)、(2,2) 这 3 个位置,橙色标出来。4 个 1 配 3 个 1,一共 12 对要枚举。
7第 1 个 img1 的 1轮到 img1 在 (0,0) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
8位移 [-1,-1]img1 的 (0,0) 对 img2 的 (1,1):位移 = (0-1, 0-1) = [-1,-1]。该位移计数变成 1。目前最高,[-1,-1] 暂列第一。
9位移 [-1,-2]img1 的 (0,0) 对 img2 的 (1,2):位移 = (0-1, 0-2) = [-1,-2]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
10位移 [-2,-2]img1 的 (0,0) 对 img2 的 (2,2):位移 = (0-2, 0-2) = [-2,-2]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
11第 2 个 img1 的 1轮到 img1 在 (0,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
12位移 [-1,0]img1 的 (0,1) 对 img2 的 (1,1):位移 = (0-1, 1-1) = [-1,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
13位移 [-1,-1]img1 的 (0,1) 对 img2 的 (1,2):位移 = (0-1, 1-2) = [-1,-1]。该位移计数变成 2。目前最高,[-1,-1] 暂列第一。
14位移 [-2,-1]img1 的 (0,1) 对 img2 的 (2,2):位移 = (0-2, 1-2) = [-2,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
15第 3 个 img1 的 1轮到 img1 在 (1,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
16位移 [0,0]img1 的 (1,1) 对 img2 的 (1,1):位移 = (1-1, 1-1) = [0,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
17位移 [0,-1]img1 的 (1,1) 对 img2 的 (1,2):位移 = (1-1, 1-2) = [0,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
18位移 [-1,-1]img1 的 (1,1) 对 img2 的 (2,2):位移 = (1-2, 1-2) = [-1,-1]。该位移计数变成 3。目前最高,[-1,-1] 暂列第一。
19第 4 个 img1 的 1轮到 img1 在 (2,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
20位移 [1,0]img1 的 (2,1) 对 img2 的 (1,1):位移 = (2-1, 1-1) = [1,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 3。
21位移 [1,-1]img1 的 (2,1) 对 img2 的 (1,2):位移 = (2-1, 1-2) = [1,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 3。
22位移 [0,-1]img1 的 (2,1) 对 img2 的 (2,2):位移 = (2-2, 1-2) = [0,-1]。该位移计数变成 2。当前最高仍是位移 [-1,-1],计数 3。
23最高位移 [-1,-1] 命中 3 次12 对全部枚举完。面板里 9 种不同位移,[-1,-1] 出现 3 次最多,其余位移都只 1 到 2 次。答案就锁在这个 3。
24这几对就是最终重叠点把贡献位移键 [-1,-1] 的 3 对 1 同时点亮:(0,0)↔(1,1)、(0,1)↔(1,2)、(1,1)↔(2,2)。注意这个键是 img1 坐标减 img2 坐标,实际移动 img1 去对齐要取相反方向,所以 [-1,-1] 对应 img1 实际向右 1、向下 1(移动哪张图只差一个相反号,计数不受影响)。这样平移后,正好这 3 个位置和 img2 重合。
25最大重叠 = 3所有位移里命中次数的最大值就是最大重叠数,这里是 3。最终答案:3。

⚠️ 容易写错的地方

✗ 错：真的去平移矩阵、还手动处理越界清零

✓ 对：不平移,只记 1 配对的相对位移并计数

越界的 1 自然配不出同一个位移,无需特判清零,代码大幅简化

✗ 错：位移方向一会儿 i-h 一会儿 h-i

✓ 对：全程固定 img1 坐标减 img2 坐标

方向混用会把同一平移拆成两个位移,计数被打散,答案偏小

✗ 错：两图无可配对 1 时对空计数取 max 报错

✓ 对：计数表为空直接返回 0

max 作用在空集合上会异常,要先判空

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

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        cnt = Counter()
        for i in range(n):
            for j in range(n):
                if img1[i][j]:
                    for h in range(n):
                        for k in range(n):
                            if img2[h][k]:
                                cnt[(i - h, j - k)] += 1
        return max(cnt.values()) if cnt else 0

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size();
        map<pair<int, int>, int> cnt;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j]) {
                    for (int h = 0; h < n; ++h) {
                        for (int k = 0; k < n; ++k) {
                            if (img2[h][k]) {
                                ans = max(ans, ++cnt[{i - h, j - k}]);
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int largestOverlap(int[][] img1, int[][] img2) {
        int n = img1.length;
        Map<List<Integer>, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (img1[i][j] == 1) {
                    for (int h = 0; h < n; ++h) {
                        for (int k = 0; k < n; ++k) {
                            if (img2[h][k] == 1) {
                                List<Integer> t = Arrays.asList(i - h, j - k);
                                ans = Math.max(ans, cnt.merge(t, 1, Integer::sum));
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
}

复杂度

时间

O(n⁴)

最坏整图都是 1,img1 的 1 与 img2 的 1 两两配对,约 n² × n² 对

空间

O(n²)

计数表里不同位移的个数,上界约 (2n-1)²

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着图像重叠的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

只枚举 1 还是 O(n⁴),能更快吗?+

为什么用位移计数比真平移再逐位比较好?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

图像重叠 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

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

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

图像重叠 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

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

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

图像重叠图解题解

图像重叠图解题解