题目描述
思路解析
一句话答案：LeetCode 718 最长重复子数组求两数组最长公共连续子数组：dp[i][j] 记以 A[i-1]、B[j-1] 结尾的公共长度，相等接左上加一、不等归零，答案取全表最大。时间 O(m·n)、空间可滚动到 O(n)。
两数组的最长公共子数组，连续这两个字卡在哪
给两个整数数组 A 和 B，要在它们里各挑出一段完全相同、而且在各自数组里连着排的片段，返回这段能有多长。题面 A=[1,2,3,2,1]、B=[3,2,1,4,7]，两边都出现过又都连续的最长片段是 [3,2,1]，长度 3。难点全压在「连续」上：中间断了一格，这段就不算数，得从断点重新数起。
把每对起点都往后比一遍为什么撑不住
一个直觉做法是把 A 的每个起点、B 的每个起点两两配对，再沿着往后逐位比对能对齐多长。A、B 各有 m、n 个起点，每对还要往后扫一趟，三层嵌套，长度一大就跑不完。相邻起点比出的前半截还大量重叠、被反复重算，把「以某两个位置结尾能对齐多长」记下来复用就能省掉。
dp[i][j] 为什么非得钉在以这两个数结尾
定义 dp[i][j] 为：A 的前 i 个数、B 的前 j 个数里，分别以 A[i-1] 和 B[j-1] 结尾的公共连续片段有多长。把结尾钉死这一步不能省——只有规定了以这两个数收尾，连续才有着落；要是定成「任意位置的最长公共片段」，中间断没断就说不清，连续这条约束会漏掉。为了下标不越界，dp 开成 (m+1)×(n+1)，第 0 行第 0 列全填 0，表示有一边没有数时公共长度只能是 0。
相等接左上加一、不等直接归零，凭什么
填 dp[i][j] 只看 A[i-1] 和 B[j-1] 这一对。它俩相等，就把这对接到上一对结尾的片段后面、长度加一，即 dp[i][j] = dp[i-1][j-1] + 1，左上那格记的正是去掉这对之后还连着的那截有多长。它俩不等，以这对结尾就连不起来，直接写 0，从这里重新数起。和最长公共子序列分道，也在这一步：子序列可以跳着挑，不等时取上、左较大的接着攒；子数组必须连续，不等就归零，一点不留。填表时随手用一个变量记下见过的最大 dp 值，就是答案。
拿 [1,2,3,2,1] 和 [3,2,1,4,7] 手填一遍
行对 A、列对 B，第 0 行第 0 列全是 0。第一行 A=1：只有对上 B 的 1 那格 dp[1][3]=dp[0][2]+1=1，其余不等全 0。第二行 A=2：对上 B 的 2，dp[2][2]=dp[1][1]+1=0+1=1。第三行 A=3：对上 B 的 3，dp[3][1]=dp[2][0]+1=1。第四行 A=2：对上 B 的 2，dp[4][2]=dp[3][1]+1=1+1=2，这里接住了上一行的 1。第五行 A=1：对上 B 的 1，dp[5][3]=dp[4][2]+1=2+1=3。全表最大值是 dp[5][3]=3，对应的正是 [3,2,1]，和答案对上。
复杂度落在哪，答案为什么不在右下角
表有 m×n 格，每格只做一次比较和一次加法，时间 O(m·n)；整表要 O(m·n) 空间，但每格只用到左上一格，倒着遍历列就能压成一维，空间降到 O(n)。别拿右下角 dp[m][n] 当答案——最长片段可能收在表里任何位置，得边填边记全局最大。不等时也别顺手写『取上、左较大』，那是子序列的转移，会把断开的片段续上；子数组这里只能归零。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
关键：dp[i][j] 必须以这两个元素结尾。这样「连续」才有保证——一旦不等就归零，重新开始数。
左上一圈先铺好 0：只要有一边没有元素，公共子数组长度就是 0。
A 的 1 和 B 的 3 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[1][1] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 1 和 B 的 2 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[1][2] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 1 和 B 的 1 相等：在左上角「上一对结尾」的 0 基础上，把这一对接上去，长度 +1。
落子：dp[1][3] = 1。每接上一对相等的数，连续公共子数组就长 1，同时刷新全局最大值。
A 的 1 和 B 的 4 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[1][4] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 1 和 B 的 7 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[1][5] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 3 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[2][1] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 2 相等：在左上角「上一对结尾」的 0 基础上，把这一对接上去，长度 +1。
落子：dp[2][2] = 1。每接上一对相等的数，连续公共子数组就长 1，同时刷新全局最大值。
A 的 2 和 B 的 1 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[2][3] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 4 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[2][4] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 7 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[2][5] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 3 和 B 的 3 相等：在左上角「上一对结尾」的 0 基础上，把这一对接上去，长度 +1。
落子：dp[3][1] = 1。每接上一对相等的数，连续公共子数组就长 1，同时刷新全局最大值。
A 的 3 和 B 的 2 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[3][2] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 3 和 B 的 1 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[3][3] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 3 和 B 的 4 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[3][4] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 3 和 B 的 7 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[3][5] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 3 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[4][1] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 2 相等：在左上角「上一对结尾」的 1 基础上，把这一对接上去，长度 +1。
落子：dp[4][2] = 2。每接上一对相等的数，连续公共子数组就长 1，同时刷新全局最大值。
A 的 2 和 B 的 1 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[4][3] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 4 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[4][4] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 2 和 B 的 7 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[4][5] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 1 和 B 的 3 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[5][1] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 1 和 B 的 2 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[5][2] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 1 和 B 的 1 相等：在左上角「上一对结尾」的 2 基础上，把这一对接上去，长度 +1。
落子：dp[5][3] = 3。每接上一对相等的数，连续公共子数组就长 1，同时刷新全局最大值。
A 的 1 和 B 的 4 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[5][4] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
A 的 1 和 B 的 7 不相等：连续被打断了，以这两个数结尾的公共子数组长度只能是 0。
落子：dp[5][5] = 0。和子序列不同——这里不取上/左较大，直接清零，因为子数组必须连续。
答案不是右下角，而是整张表里的最大值：dp[5][3] = 3，对应公共子数组 [3,2,1]。
边界先想清。
两个高频追问。
参考代码
def findLength(A, B): m, n = len(A), len(B) dp = [[0]*(n+1) for _ in range(m+1)] ans = 0 for i in range(1, m+1): for j in range(1, n+1): if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 ans = max(ans, dp[i][j]) return ans复杂度
- 时间：O(m·n)，每格 O(1)，共 m×n 格
- 空间：O(m·n)，整表；因只依赖上一行，可滚动到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么答案是全表最大值而不是 dp[m][n]？
追问能优化空间吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删除并获得点数
LeetCode 740 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题