LeetCode 835「图像重叠」全解：从 81 万次比较到 FFT 互相关，五种解法的实测与六个坑

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

LeetCode 835「图像重叠」全解：从 81 万次比较到 FFT 互相关，五种解法的实测与六个坑

题目给两个 n×n 的 0/1 矩阵，允许把其中一个整体平移（上下左右任意格数，越界即丢弃），问两图\”同为 1\”的位置最多有多少个。n ≤ 30。

这篇不是\”背一个模板\”的文章。835 真正的价值在于：它小到暴力能过（n=30 只有 81 万次比较），又大到足以把三种完全不同的思路——枚举位移、枚举 1 的坐标对、把平移看成卷积——各自的真实代价完整地暴露出来。本文把这五种解法都写出来、都跑起来、都在三种密度下打一遍分，最后给出它们在 n=30 之外（n=480、n=960）的规模曲线，以及六个我实际踩到、并且都找到了最小反例的坑。

目录

• 1 题目重述与形式化建模

  • 1.1 三个示例的逐步验算

  • 1.2 把\”平移\”翻译成坐标差

  • 1.3 一个反直觉的结论：越界根本不用处理

  • 1.4 答案的上下界

• 2