LeetCode 835. 图像重叠
目录
题目描述
题意分析
给定两个 $n \times n$ 的二值矩阵
img1与img2。可以把img1整体向上下左右平移任意格数（不能旋转、不能翻转），移出边界的部分直接丢弃。平移之后，统计有多少个位置上两个矩阵都是 1，这个数量称为重叠数。求所有平移方案中最大的重叠数。「只能平移、不能旋转翻转」把变换空间限制成了一个二维的偏移量 $(dx, dy)$。这是解题的第一个立足点：答案完全由偏移量决定，所以问题变成「在所有可能的偏移量中，哪个能让 1 重合得最多」。
「移出边界的部分丢弃」看似要小心处理，实际上它自动被「重叠数只统计两矩阵都为 1 的位置」这条规则消化掉了——移出去的 1 不可能与任何位置重合，自然不会被计入。所以实现时不需要显式处理裁剪。
约束是 $1 \le n \le 30$。矩阵最多 900 个格子，1 的个数最多也是 900。这个规模允许两种做法：枚举全部 $(2n-1)^2 \approx 3481$ 个偏移量、每个偏移量花 $O(n^2)$ 验证，总计约 $3 \times 10^6$；或者只对 1 的位置做两两配对，$900 \times 900 = 8.1 \times 10^5$。后者在稀疏矩阵上快得多，且实现更短。
边界方面：两个矩阵可能全是 0，此时答案是 0，任何实现都要能返回 0 而不是崩溃或返回负值；偏移量为 $(0,0)$（不平移）也是一种合法方案，不能被排除。
解法：统计 1 点差向量（哈希计数）
核心思路
最直接的做法是枚举偏移量：让 $dx$ 从 $-(n-1)$ 取到 $n-1$、$dy$ 同理，对每一对 $(dx, dy)$ 遍历整个矩阵统计重合数。这是对的，$O(n^4)$ 在 $n = 30$ 时约三百万次操作，能过。但它有一个明显的浪费：绝大多数格子是 0，对答案毫无贡献，却被反复扫描了三千多遍。
瓶颈找到了：应该只关心 1 的位置。把
img1中所有 1 的坐标收集成集合 $A$，img2中所有 1 的坐标收集成集合 $B$。平移img1相当于给 $A$ 中每个点加上同一个偏移向量 $(dx, dy)$，而重叠数就是
$ {(dx+a_x,\ dy+a_y) : (a_x,a_y) \in A} \cap B $ 换句话说，一个点 $a \in A$ 在偏移 $(dx,dy)$ 下能与某个 $b \in B$ 重合，当且仅当 $b - a = (dx, dy)$。
这句话把问题彻底翻转了：与其枚举偏移量再去数有多少对点重合，不如枚举所有的点对 $(a, b)$，算出它们各自「需要」的偏移量 $b - a$，然后看哪个偏移量被最多的点对需要。每一对 $(a,b)$ 恰好对应唯一一个偏移量，而某个偏移量下的重叠数，恰好等于「差向量等于它」的点对数量。两者是严格的一一对应，所以取计数的最大值就是答案。
这就是「按贡献计数」的思路：不枚举答案的候选，而是枚举产生贡献的最小单元，再按它们归属的候选分类计数。
于是显式写下要维护的状态：一个哈希计数表，键是差向量 $(dx, dy)$，值是「差向量恰好等于它的 $(a,b)$ 点对数量」，也就是该偏移量下的重叠数。 一边枚举点对一边累加，同时用一个变量跟踪计数的最大值，扫完即得答案。
几处实现细节：
差向量的方向必须固定。 取 $b - a$（用
img2的坐标减img1的坐标），因为我们平移的是img1，要让 $a$ 移动到 $b$ 的位置。反过来取 $a - b$ 也能得到正确的最大值（因为整个计数表只是关于原点做了对称），但如果题目要求输出偏移量本身，方向就错了；更重要的是同一份代码里方向必须前后一致。差向量的分量可以是负数，范围是 $[-(n-1), n-1]$。用哈希表存二元组时要能容纳负数。Java 里把两个 32 位整数拼成一个 64 位的键，需要对低位做无符号掩码，避免负的 $dy$ 通过符号扩展污染高 32 位；Go 里可以直接用长度为 2 的数组作为键，语言原生支持数组作可比较类型，最省心。
答案的初值取 0。全零矩阵时一个点对都没有，循环体不执行，返回 0，恰好正确；这也覆盖了「无论怎么平移都无法重合」的情形。
顺带一提，
img1平移与img2平移是等价的：把img1移动 $(dx,dy)$ 与把img2移动 $(-dx,-dy)$ 得到相同的重叠数，所以题目只让平移一个矩阵并不损失一般性。
解题步骤
- 第一步，扫描两个矩阵，把各自 1 的坐标分别收集到列表 $A$ 与 $B$。 为什么先提取坐标：后续只需要 1 的位置，0 的格子对任何偏移量都没有贡献。提取之后，复杂度从与格子数相关变成与 1 的个数相关，稀疏输入下收益巨大。为什么可以在同一个双重循环里同时收集两个矩阵：两个矩阵同尺寸，一趟扫描即可，省掉一次遍历。
- 第二步，准备一个「差向量 → 计数」的哈希表和一个答案变量（初值 0）。 为什么答案初值取 0：矩阵可能全零，此时没有任何点对，必须返回 0；同时重叠数本身也不可能为负。
- 第三步，双重循环枚举每一对 $(a, b)$，其中 $a \in A$、$b \in B$。 为什么要枚举所有点对而不是只枚举「看起来靠近」的点对：任何一对 1 都可能在某个平移下重合，没有可以先验排除的组合。
- 第四步，计算差向量 $dx = b_x - a_x$、$dy = b_y - a_y$，作为键。 为什么是 $b$ 减 $a$：平移的是
img1，我们要求的是「把 $a$ 搬到 $b$ 需要的位移」。方向必须全程一致，否则同一个偏移量会被拆成两个不同的键。- 第五步，把该键的计数加一，并用新计数更新答案的最大值。 为什么可以边累加边取最大：计数只增不减，任何时刻的最大值就是已处理点对中的最优；不必等全部统计完再遍历哈希表求最大，省一次遍历。
- 第六步，返回答案。
以
img1 = [[1,1,0],[0,1,0],[0,1,0]]、img2 = [[0,0,0],[0,1,1],[0,0,1]]走一遍（$n = 3$，期望答案 3）。提取坐标：
img1中值为 1 的位置是 $A = {(0,0),\ (0,1),\ (1,1),\ (2,1)}$；img2中值为 1 的位置是 $B = {(1,1),\ (1,2),\ (2,2)}$。共 $4 \times 3 = 12$ 对点。枚举点对并累加差向量：
$a = (0,0)$：与 $(1,1)$ 得差向量 $(1,1)$，计数变 1，答案更新为 1；与 $(1,2)$ 得 $(1,2)$，计数 1；与 $(2,2)$ 得 $(2,2)$，计数 1。
$a = (0,1)$：与 $(1,1)$ 得 $(1,0)$，计数 1；与 $(1,2)$ 得 $(1,1)$，该键计数变成 2，答案更新为 2；与 $(2,2)$ 得 $(2,1)$，计数 1。
$a = (1,1)$：与 $(1,1)$ 得 $(0,0)$，计数 1；与 $(1,2)$ 得 $(0,1)$，计数 1；与 $(2,2)$ 得 $(1,1)$，该键计数变成 3，答案更新为 3。
$a = (2,1)$：与 $(1,1)$ 得 $(-1,0)$，计数 1；与 $(1,2)$ 得 $(-1,1)$，计数 1；与 $(2,2)$ 得 $(0,1)$，该键计数变成 2，不超过当前答案 3。
最终计数表中 $(1,1)$ 这个差向量出现了 3 次，是唯一的最大值，返回 3。
验证：偏移量 $(1,1)$ 表示把
img1向下移一行、向右移一列。img1中的三个点 $(0,0)$、$(0,1)$、$(1,1)$ 分别落到 $(1,1)$、$(1,2)$、$(2,2)$，这三个位置在img2中都是 1，重合 3 个；剩下的点 $(2,1)$ 移到 $(3,2)$ 已经出界，被丢弃——注意我们完全没有为出界写任何代码，它只是没有出现在任何一对匹配里，这正是「不必显式裁剪」的体现。这个例子还说明了负数键的必要性：$a = (2,1)$ 产生了 $(-1,0)$ 和 $(-1,1)$ 两个差向量，它们对应把
img1向上移动。虽然本例中它们不是最优解，但在别的输入里最优偏移完全可能是负的，键的表示必须支持负数。
代码实现
class Solution {
public int largestOverlap(int[][] img1, int[][] img2) {
List<int[]> a = new ArrayList<>();
List<int[]> b = new ArrayList<>();
int n = img1.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (img1[i][j] == 1) {
a.add(new int[] {i, j});
}
if (img2[i][j] == 1) {
b.add(new int[] {i, j});
}
}
}
Map<Long, Integer> cnt = new HashMap<>();
int answer = 0;
for (int[] pa : a) {
for (int[] pb : b) {
int dx = pb[0] - pa[0];
int dy = pb[1] - pa[1];
long key = (((long) dx) << 32) ^ (dy & 0xffffffffL);
int v = cnt.getOrDefault(key, 0) + 1;
cnt.put(key, v);
answer = Math.max(answer, v);
}
}
return answer;
}
}
type Point struct{ x, y int }
func largestOverlap(img1 [][]int, img2 [][]int) int {
a := make([]Point, 0)
b := make([]Point, 0)
n := len(img1)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if img1[i][j] == 1 {
a = append(a, Point{x: i, y: j})
}
if img2[i][j] == 1 {
b = append(b, Point{x: i, y: j})
}
}
}
cnt := make(map[[2]int]int)
answer := 0
for _, pa := range a {
for _, pb := range b {
dx := pb.x - pa.x
dy := pb.y - pa.y
key := [2]int{dx, dy}
cnt[key]++
if cnt[key] > answer {
answer = cnt[key]
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n^2 + p \cdot q)$，其中 $p$、$q$ 分别是两个矩阵中 1 的个数，均不超过 $n^2$。提取坐标扫一遍是 $O(n^2)$；点对枚举是 $O(pq)$，每对只做两次减法和一次哈希操作。最坏（矩阵全 1）时是 $O(n^4)$，$n = 30$ 约 $8 \times 10^5$；而稀疏输入下 $p$、$q$ 很小，远快于「枚举 $(2n-1)^2$ 个偏移量、每个花 $O(n^2)$ 验证」的固定 $3 \times 10^6$。
- 空间复杂度：$O(p + q)$。两个坐标列表各自占用与 1 的个数同阶的空间；哈希表的键数不超过点对数，但实际上不同差向量最多只有 $(2n-1)^2 \approx 3481$ 个，所以它是 $O(n^2)$ 上界内的常数级结构。
关键点总结
- 变换空间是低维参数时，把「枚举变换」翻转成「枚举贡献」。平移只由 $(dx,dy)$ 两个参数决定，每一对 1 恰好「投票」给唯一一个偏移量。与其对每个偏移量重新扫描全图，不如让点对自己去认领偏移量，再取票数最高的。这个翻转把 $O(n^4)$ 变成了与 1 的密度相关的 $O(pq)$。
- 只保留有效元素的坐标，忽略无贡献的空位。二值矩阵题里，0 往往完全不参与答案。先把 1 的坐标抽出来，复杂度立刻从「与网格规模相关」变成「与有效元素个数相关」，稀疏数据上收益极大。
- 出界裁剪常常可以由「只统计重合」自动消化。移出边界的 1 不会与任何位置配对，所以不写任何裁剪代码也不会算错。遇到「超出部分丢弃」的描述，先想想它会不会自动落空，能省掉一整块边界处理。
- 二维键要正确编码负数。差向量的分量可正可负，Java 里拼 64 位键必须对低 32 位做无符号掩码
dy & 0xffffffffL，否则负数的符号扩展会把高位全填 1，导致不同的 $(dx,dy)$ 撞成同一个键。Go 里直接用固定长度数组作键最安全。- 边累加边取最大值可以省掉一次遍历。计数单调递增，所以每次更新后立刻比较就能维护全局最大，不必等统计完再遍历哈希表。凡是「先计数再求最值」的模式，都可以这样合并。
- 面试视角：这题面试官想听的是从「枚举偏移量」到「枚举点对」的转换动机。开口先给出朴素的 $O(n^4)$ 并算出量级，再指出「大量 0 被反复扫描」这个浪费，然后抛出「每对 1 决定唯一一个偏移量」的观察——这条推理链完整了，代码就是十几行。常见追问有三个：一是「负偏移怎么表示」，答键要能容纳负数分量并说明 Java 的掩码写法；二是「哪种做法更快」，答取决于 1 的密度，稀疏时点对法完胜、稠密时两者同阶；三是「如果允许旋转呢」，正确回答是把
img1的四个旋转版本各跑一遍取最大，因为旋转只有四种离散可能，可以外层枚举。
易错点总结
- 错误写法：Java 里拼 64 位键时不对低位做无符号掩码，写成
(((long) dx) << 32) | dy。以差向量 $(1, -1)$ 与 $(0, -1)$ 为例，$dy = -1$ 的符号扩展会把高 32 位全部置 1，两个本应不同的键会被或运算污染成相同的值，计数被错误合并，答案偏大。必须写成(dy & 0xffffffffL)。- 错误写法：差向量的方向前后不一致，一处写 $b - a$、另一处写 $a - b$。以本文的例子为例，$(0,0)$ 与 $(1,1)$ 配对时若算成 $(-1,-1)$，而 $(1,1)$ 与 $(2,2)$ 配对时算成 $(1,1)$，同一个平移方案的票数被拆到两个键上，最大值从 3 掉到 2。方向必须全程固定。
- 错误写法：把 $dx$、$dy$ 直接拼成字符串键但不加分隔符，例如
"" + dx + dy。以 $(1, 12)$ 与 $(11, 2)$ 为例，两者都拼成"112"，不同的偏移量撞键，计数错误合并。字符串键必须有明确的分隔符，或干脆用结构化的键。- 错误写法：答案初值设为 1 或负数。以两个全零矩阵为例，循环体一次都不执行，初值直接被返回；设成 1 会返回 1，而正确答案是 0。重叠数的下界就是 0。
- 错误写法：只枚举非负的偏移量。以需要把
img1向上或向左平移的输入为例（比如img1的 1 集中在右下、img2的集中在左上），最优偏移的分量为负，只统计非负键会漏掉它，答案偏小。平移是四个方向都允许的。- 错误写法：为了「处理出界」而在配对前判断 $a + (dx,dy)$ 是否越界。以本文的例子为例，配对本身就要求 $b$ 是一个真实存在的格子，$a + (dx,dy) = b$ 必然在界内，额外的判断永远为真，纯属多余；而如果判断写反（比如误判成越界就跳过），反而会漏掉合法配对。出界由「配对不上」自动消化。
- 错误写法：只收集
img1的 1 坐标，对img2仍然按格子遍历判断。以稀疏矩阵为例，这会让复杂度退回 $O(p \cdot n^2)$，失去了大半优化；更常见的问题是两套索引方式混用导致下标写错。两个矩阵应对称处理。- 错误写法：统计完所有点对后再遍历哈希表求最大值，但遍历时用了
values()的类型转换失误。这在逻辑上没错，只是多一次遍历；真正的风险是忘记处理哈希表为空的情形（全零矩阵），此时求最大值会得到一个未定义的初值或抛异常。边累加边比较可以规避这个分支。- 错误写法：Go 里用
map[Point]int而Point定义包含切片或指针字段。以任意输入为例，含不可比较字段的结构体不能作为映射的键，编译报错。本代码用的是纯整型字段的固定数组作键，是安全的写法。- 错误写法：认为「平移 img1」与「平移 img2」需要分别算两遍取最大。以任意输入为例，把
img1移动 $(dx,dy)$ 与把img2移动 $(-dx,-dy)$ 得到完全相同的重合集合，两遍统计结果的最大值一致，第二遍纯属重复劳动。- 错误写法：把「重叠」理解成「两矩阵对应位置相同」（包括都是 0）。以两个全零矩阵为例，按这个理解答案会是 $n^2$，而正确答案是 0。题目只统计两边都为 1 的位置。
- 错误写法：坐标收集时把行列写反，
a.add(new int[]{j, i})。以非对称的输入为例，相当于对img1做了转置，得到的是「转置后再平移」的最大重合数，与题意不符；由于矩阵是方阵，程序不会崩溃，只会静默给出错误答案，极难发现。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 同样枚举点对并把「斜率」哈希计数取最大，但要处理约分与垂直线的表示 |
| 447. 回旋镖的数量 | 中等 | 以每个点为中心统计到其余点的距离并按距离计数，是「枚举点对 + 归类计数」的变体 |
| 1. 两数之和 | 简单 | 用哈希表把「配对关系」压成一次查询，是本题差向量思路的一维雏形 |
| 48. 旋转图像 | 中等 | 矩阵的另一类变换，重点在原地旋转的下标映射而非统计 |
| 221. 最大正方形 | 中等 | 二值矩阵上的最优子结构 DP，可对照「什么时候该 DP、什么时候该枚举计数」 |
| 1074. 元素和为目标值的子矩阵数量 | 困难 | 压缩一维后用前缀和哈希计数，同样是「把二维问题化归成可哈希的键」 |
| 223. 矩形面积 | 中等 | 求两个矩形的重叠面积，用坐标区间交集直接算，是重叠概念的连续版本 |