刷力扣718的时候我第一反应是这不就是最长公共子序列换了个皮等我把题目仔细读完“子数组”三个字直接让我清醒了。子数组要求连续子序列不要求这一字之差状态转移方程差得不是一星半点。718题是求两个整数数组中最长的重复子数组长度面试里出现频率不低而且从二维DP到滚动数组优化再到滑动窗口能考的点特别多。这篇内容我按自己刷题复盘的方式整理了一遍Java实现为主把状态定义、转移推导、空间优化和常见坑一次说清楚适合刚接触动态规划的读者也适合准备面试想快速过思路的人。1. 题目拆解子数组和子序列的差别在哪里1.1 为什么“连续”让题目难度直接不同先说子数组的定义。子数组是原数组中连续的一段比如数组 [1,2,3,2,1] 里[2,3,2] 是子数组但 [1,3,2] 不是因为它跳过了下标1的2。子序列则只要求保持相对顺序不要求连续所以 [1,3,2] 在子序列定义下是合法的。这两个概念放到动态规划里差别体现在“断点怎么处理”。求最长公共子序列时如果当前位置元素不相等dp 可以从上边或左边继承一个最大值因为中间可以跳过元素继续匹配。但最长重复子数组一旦遇到不相等的元素之前累计的连续匹配就全部作废必须从0重新开始。这个“归零”操作正是这道题和1143题最大的分水岭。我见过不少同学刷完1143再来做718顺手就把 max 逻辑写在 else 分支里结果样例能过一到大数据就错。根本原因就是没有理解“连续”对状态转移的约束连续匹配就像两个人必须从同一站上地铁中间不能下车换乘一旦有人到站下车前面一起坐过的距离就断了得重新计时。1.2 手推一个用例先明确输出题目给的经典例子是 A [1,2,3,2,1]B [3,2,1,4,7]。我们用手工方式找一遍。把两个数组对齐肉眼扫A 里的 [3,2,1] 正好对应 B 的开头 [3,2,1]长度3这是最长的。[2,1] 也是公共子数组长度2但不如3长。单个数字 [1]、[2] 也都匹配但长度只有1。所以答案是3。注意题目只要求返回长度不要求返回具体是哪个子数组。如果之后扩展成“返回最长公共子数组本身”就需要额外记录最长长度出现的位置后面章节我会单独提。再举一个容易混淆的例子A [1,2,3]B [2,3,1]。公共子数组有 [2,3] 长度2这里没有长度为3的公共段因为A的1开头在B的末尾连不成长度为3的连续段。所以答案是2。这类用例能帮你确认算法是不是真的要求“连续”而不是把1,2,3当作子序列拼出来。1.3 暴力法复杂度先心里有数最朴素的暴力做法是枚举A的每个起点 i枚举B的每个起点 j然后从 i 和 j 同时向后扫描记录连续相等的最大长度。public int findLengthBruteForce(int[] A, int[] B) { int n A.length, m B.length; int max 0; for (int i 0; i n; i) { for (int j 0; j m; j) { int k 0; while (i k n j k m A[i k] B[j k]) { k; } max Math.max(max, k); } } return max; }这个代码逻辑是对的但复杂度很高最外层两个循环是 O(nm)while 循环最多还能跑 min(n,m) 次所以整体是 O(nm*min(n,m))。当 n 和 m 都到1000时理论最坏接近10^9次比较本地跑起来都很吃力力扣的数据规模稍大一点直接超时。不过暴力法的思路本身有用它告诉我们“连续相等段的长度”是核心动态规划就是把这个重复比较的过程用空间换时间把已经算过的匹配长度存下来。2. 动态规划解法从状态定义到Java实现2.1 别急着写代码先把dp[i][j]想明白动态规划最怕一上来就背状态转移。718这题状态定义直接用“以某个位置结尾的公共后缀长度”最顺。定义 dp[i][j] 表示 A 的前 i 个元素和 B 的前 j 个元素中以 A[i-1] 和 B[j-1] 为结尾的公共子数组长度。为什么用“以”结尾而不是“从开头到当前位置的最大值”因为连续子数组的匹配是向后延伸的我们需要知道“当前两个元素如果相等之前连续匹配到了多长”这个信息只有“以什么结尾”的状态能提供。如果定义成“A[0..i-1] 和 B[0..j-1] 之间的最长公共子数组长度”那么当 A[i-1] ! B[j-1] 时你很难确定要不要继承前面的值——继承的话可能把不连续的部分接起来不继承又会丢掉右边可能还没匹配到的最优值。这个状态定义不是不能做但转移条件会复杂很多。所以别给自己找麻烦就用“公共后缀长度”。2.2 状态转移式和边界条件的推导有了定义转移方程就顺理成章如果 A[i-1] B[j-1]说明当前两个元素匹配上了可以把前面已经匹配的连续段接上dp[i][j] dp[i-1][j-1] 1。如果 A[i-1] ! B[j-1]说明连续匹配在这里断掉公共后缀长度直接归零dp[i][j] 0。答案不是 dp[n][m]因为最长公共子数组不一定以两个数组的末尾结尾它可能出现在中间任意位置。所以每次更新 dp[i][j] 后都要用 max 记录全局最大值。边界条件也简单dp[0][j] 表示 A 为空数组dp[i][0] 表示 B 为空数组空数组和任何数组的公共后缀长度都是0所以 dp 数组初始化为0即可。为了验证拿 A [1,2,3]B [1,2,3] 手工填一遍表。第一行 i1A[0]1和 B 的1匹配时 dp[1][1]1和后面的2、3不匹配所以 dp[1][2]0dp[1][3]0。第二行 i2A[1]2与 B[1]2 匹配时 dp[2][2]dp[1][1]12注意这里 dp[1][1] 来自于上一行的左上角正好表示之前的1匹配上了。第三行同理得到 dp[3][3]3。最终 max3。2.3 二维DP的Java完整实现直接给可以运行的代码class Solution { public int findLength(int[] A, int[] B) { int n A.length; int m B.length; int[][] dp new int[n 1][m 1]; int max 0; for (int i 1; i n; i) { for (int j 1; j m; j) { if (A[i - 1] B[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; max Math.max(max, dp[i][j]); } else { dp[i][j] 0; } } } return max; } }注意两点。第一dp 的长度是 n1 和 m1循环从1开始访问 A[i-1] 而不是 A[i]这样 dp[i-1][j-1] 在 i1 或 j1 时不会越界。第二不匹配时一定要显式置0虽然 int 数组默认是0但第一次不置0没问题后续行如果不清零就会把上一行的旧值残留下来导致错误地延续匹配。这段代码提交力扣时间复杂度 O(nm)空间复杂度 O(nm)。在 n、m 都等于1000左右时内存大约几个MB没问题。但如果你遇到的变体题数据范围是10^4二维数组就不行了必须做空间优化。2.4 时空复杂度二维数组为什么不够优雅假设 nm10000dp 数组元素个数是 10000*10000 1亿每个 int 占4字节总内存约400MB严重超出常规内存限制。即便 nm5000也有100MB左右很多场景下同样危险。所以面试里问完二维DP基本都会追问一句“能不能优化空间”。这个优化的方向很明确计算 dp[i][j] 时只用了 dp[i-1][j-1]也就是上一行的左上角数据。换句话说我们根本不需要把整个二维表都记住只需要保留上一行的值就能推出当前行。这就是滚动数组的动机。3. 空间优化一行数组也能跑关键是遍历顺序3.1 滚动数组的核心逻辑和常见误区滚动数组的思路是用一维数组 dp[j] 表示当前行处理到A的第 i 个元素时以 B[j-1] 结尾的公共后缀长度。每遍历A的一个元素我们就更新整个一维数组让数组从上一行状态变成当前行状态。这里最大的坑就是遍历顺序。如果你把二维数组的循环直接改成下面这样// 错误示范 for (int i 1; i n; i) { for (int j 1; j m; j) { if (A[i - 1] B[j - 1]) { dp[j] dp[j - 1] 1; } else { dp[j] 0; } } }j 从左到右更新结果往往是错误的。原因很简单dp[j] 的计算需要的是“上一行”的 dp[j-1]也就是 dp[i-1][j-1]。但当你从左往右更新时dp[j-1] 已经在当前行被更新过了它现在是 dp[i][j-1]而不是 dp[i-1][j-1]。于是你把“当前行已经匹配的右侧长度”当成了“上一行的左侧长度”连续匹配就被重复累加了。这种错误非常隐蔽因为少量数据可能碰巧没事数据一特殊就崩。比如 A 和 B 都是 [1,1,1] 时正确结果应该是3但错误滚动更新会让结果偏大。3.2 倒序更新的Java实现推荐解决办法就是让 j 从 m 往1遍历。倒序时更新 dp[j] 之前dp[j-1] 还没有被当前行覆盖仍然保留着上一行的值也就是 dp[i-1][j-1]正好是我们需要的。代码class Solution { public int findLength(int[] A, int[] B) { int n A.length; int m B.length; int[] dp new int[m 1]; int max 0; for (int i 1; i n; i) { for (int j m; j 1; j--) { if (A[i - 1] B[j - 1]) { dp[j] dp[j - 1] 1; max Math.max(max, dp[j]); } else { dp[j] 0; } } } return max; } }这个写法空间复杂度降到了 O(m)。如果你希望空间尽可能小可以让 dp 的长度使用两个数组长度中较小的那个遍历时把较短数组放在内层这样空间是 O(min(n,m))。倒序更新的关键点dp[0] 永远保持0它表示 B 的空前缀在任何一行都不会被更新。j1 时 dp[1] dp[0] 1正好对应 A[i-1] 和 B[0] 相等时长度为1的情况。3.3 pre变量法的实现与对比如果你觉得倒序不太直观也可以从左到右遍历但需要一个变量提前保存左上角的值。这种写法在不少教材里叫“prev 游标法”。class Solution { public int findLength(int[] A, int[] B) { int n A.length; int m B.length; int[] dp new int[m 1]; int max 0; for (int i 1; i n; i) { int prev 0; for (int j 1; j m; j) { int temp dp[j]; if (A[i - 1] B[j - 1]) { dp[j] prev 1; max Math.max(max, dp[j]); } else { dp[j] 0; } prev temp; } } return max; } }解释一下 prev 的流动过程进入第 i 行后dp[j] 存的是上一行第 j 个位置的值。在循环里prev 表示 dp[i-1][j-1]当 j1 时prev 是0对应 dp[i-1][0]。更新 dp[j] 前先用 temp 保存 dp[j] 的旧值因为下一轮 j1 需要的是 dp[i-1][j]也就是当前这个 j 的上一行值不能让它被覆盖掉。更新完 dp[j] 后把 prev temp这样下一轮循环 prev 就变成了 dp[i-1][j]正好是 j1 的左上角。对比一下倒序法代码更短但理解门槛稍高pre变量法符合从左到右的自然习惯但多几行代码且容易忘记保存旧值。就面试而言我更推荐倒序法因为解释了原理之后很好记忆手写也不容易错。3.4 用两个例子验证一维优化拿 A[1,2,3]B[1,2,3] 手动跑一遍倒序更新确保没有理解偏差。初始 dp 全0max0。 i1A[0]1。j3A[0]!B[2]3dp[3]0j2A[0]!B[1]2dp[2]0j1A[0]B[0]1dp[1]dp[0]11max1。 此时 dp[0,1,0,0]。 i2A[1]2。j3不匹配dp[3]0j2A[1]B[1]2dp[2]dp[1]12max2j1A[1]!B[0]1dp[1]0。 此时 dp[0,0,2,0]。 i3A[2]3。j3匹配dp[3]dp[2]13max3j2不匹配dp[2]0j1不匹配dp[1]0。 结果正确。再验证不匹配的情况A[1,2]B[3,4]。 i1A[0]1j2不匹配 dp[2]0j1不匹配 dp[1]0。i2同理全程dp保持0max0。注意如果不匹配时不置0dp里残留的上一行值会让后续匹配变长这就是必须显式清零的原因。4. 另一种思路滑动窗口对齐法4.1 对齐偏移量的思想动态规划不是唯一解法。最长重复子数组还可以用“滑动窗口对齐”的思路来理解把两个数组想象成两条刻度尺固定其中一个让另一个从左到右慢慢滑动。每次滑动后比较两个数组重叠区域中相同位置的数字连续相同时就累计长度遇到不同就清零记录过程中的最大值。所谓“偏移量”就是 B 数组相对于 A 数组左移或右移的位数。每一个偏移量对应一次对齐。对每个偏移重叠区间内的比较顺序是固定的不存在回溯所以不需要额外空间。这种方法的直观优势是省内存。难点在于偏移量的枚举和对齐边界的处理但代码写顺了之后其实比DP更符合直觉。4.2 滑动窗口的Java实现比较清晰的写法是枚举“A 的每个起点与 B 的第0个位置对齐”以及“B 的每个起点与 A 的第0个位置对齐”覆盖所有偏移。每次从给定起点同时向后比较直到其中一个数组越界。class Solution { public int findLength(int[] A, int[] B) { int n A.length; int m B.length; int max 0; for (int i 0; i n; i) { max Math.max(max, check(A, B, i, 0)); } for (int j 0; j m; j) { max Math.max(max, check(A, B, 0, j)); } return max; } private int check(int[] A, int[] B, int aStart, int bStart) { int max 0; int len 0; int i aStart; int j bStart; while (i A.length j B.length) { if (A[i] B[j]) { len; max Math.max(max, len); } else { len 0; } i; j; } return max; } }这段代码看起来简单但有一个容易忽略的点check 返回的是这个对齐方式下的最大连续段长度而不是重叠区末尾的 len。比如某次对齐中前面匹配了3个后面突然不匹配接着又匹配了2个max 应该是3。如果直接返回 len就会漏掉前面更长的段所以必须用 max 记录。时间复杂度的估算第一种循环枚举A的起点第二种循环枚举B的起点总共枚举约 nm 次对齐每次对齐最多比较 min(n,m) 个元素所以整体约 O((nm)*min(n,m))。空间复杂度 O(1)。当 n 和 m 都接近10^5 时这个方法仍然可能超时但在长度几千的情况下实测表现往往比二维DP更轻快因为不需要维护额外矩阵。4.3 DP vs 滑动窗口怎么选我把这题常见的解法放在一起对比过直接列个表方法时间复杂度空间复杂度代码量适合场景二维DPO(n*m)O(n*m)最少数据规模小先写出来保底一维滚动DPO(n*m)O(min(n,m))中等面试首选思路稳定滑动窗口O((nm)*min(n,m))O(1)稍多内存受限或者想展示多思路二分哈希O((nm)log(min(n,m)))O(n)较多进阶向追求理论更优实际刷题时我基本默认写一维滚动DP。原因很简单DP的转移方程对这类“连续匹配”问题非常通用改动几个条件就能解决不少变体题。但面试官如果接着问“能不能不用DP用别的思路”滑动窗口就是一个很好的补充答案。它不依赖状态表而是直接枚举对齐位置体现你对“重复子数组连续相等”本质的理解。5. 进阶玩法二分滚动哈希选读5.1 二分答案哈希检查的思路这个方法属于竞赛向进阶不是所有面试都会考但用来开拓思路很不错。核心观察是如果存在长度为 L 的公共重复子数组那么一定存在长度小于 L 的公共重复子数组反过来如果长度为 L 的公共子数组不存在那么长度大于 L 的也一定不存在。所以答案具有单调性可以二分查找最大长度 L。二分框架确定后剩下的问题是 check(L)如何快速判断两个数组中是否存在长度为 L 的公共子数组最直接的办法是把 A 中所有长度为 L 的连续段哈希值放进一个集合然后遍历 B 中所有长度为 L 的连续段只要某个哈希值出现在集合里就说明找到了相同段。这里用哈希而不是直接比较字符串是为了把 O(L) 的段比较变成 O(1) 的哈希值比较。计算所有长度为 L 的段哈希值时可以用滚动哈希也就是 Rabin-Karp 的核心思想。5.2 Rolling Hash的注意点与扩展滚动哈希的公式不复杂。设 base 是一个大于元素值域的素数hash hash * base value。已知长度为 L 的窗口哈希值要向右滑动一格先减去头部元素贡献的 hash * base^L再乘 base 加上新元素。Java 里可以选择 long 自然溢出但碰撞概率不是零如果做竞赛题建议用双哈希或者两个大质数取模降低碰撞风险。不过这道题的数据范围通常不需要走到二分哈希这一步除非你准备算法竞赛或者被问到“能不能做到 O((nm)logL)”。面试时如果提到这个方法能说出“二分答案 Rolling Hash 单调性”三个关键词已经足够证明你有广度。至于完整代码篇幅比较长这里就不贴了真感兴趣可以拿 Rabin-Karp 的模板练一遍字符串匹配原理是相通的。6. 实战踩坑与面试建议6.1 我见过的三类经典bug第一类bug是把子数组当子序列做。有人把状态转移写成if (A[i - 1] B[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]); }这样返回的是最长公共子序列长度不是最长公共子数组。区别就在 else 分支子数组要求连续所以必须归零不能从旁边继承。这个错误很隐蔽因为样例短的时候公共子序列和公共子数组可能刚好一样长。第二类bug是一维滚动数组正向更新。前面已经详细解释过正向更新会让当前行已经更新的 dp[j-1] 被误当成上一行数据导致结果虚增。我记得有次在本地测试用例都通过提交以后发现某些边界用例报错后来打印中间数组才定位到遍历顺序问题。从那以后凡是涉及“只依赖左上方”的滚动更新我都默认倒序不给自己留犯错的余地。第三类bug是 dp 数组长度没多开1。有人写成 int[][] dp new int[n][m]循环从 i0,j0 开始然后访问 dp[i-1][j-1]i0 时就数组越界了。为了规避只能写一堆 if 判断代码丑且容易漏。不如老老实实多开一列一行用 i1..n 对应 A[i-1]逻辑清白边界也天然处理好了。6.2 面试时如何把这道题讲到加分面试官问这道题其实想听到的是一条思考链路而不是最终代码。你可以这样讲先说暴力法枚举所有起点组合并向后比较复杂度 O(nmmin(n,m))太慢然后意识到连续匹配可以复用之前的结果于是想到动态规划。定义 dp[i][j] 为以 A[i-1] 和 B[j-1] 结尾的公共后缀长度因为连续匹配的延伸只关心上一次是否相等。当前相等则从 dp[i-1][j-1] 加1不相等则清零。这样得到二维DP时间 O(nm)空间 O(nm)。接着观察到每一行只依赖上一行的左上角于是用一维数组倒序更新空间降到 O(min(n,m))。最后可以补一句“如果不用DP还可以通过枚举偏移量做滑动窗口比较空间复杂度O(1)。”这就展示了你有多种思路而且不是死记硬背。6.3 刷题复盘这道题值得二刷三刷的点在哪里718这道题虽然叫“最长重复子数组”本质上就是两个数组的最长公共连续段。二刷的时候我建议你重点做三件事第一把滚动数组的一维版本默写三遍确保倒序遍历的顺序不会搞错。第二用滑动窗口法再写一遍体会无额外空间的解法里边界条件怎么处理。第三想两个扩展如果题目要求返回最长子数组本身怎么记录结束位置如果两个数组换成字符串代码怎么改。字符串版本就是“最长公共子串”工程上很常见所以718值得多花点时间。我刷这道题踩过正向更新的坑之后总结出一条经验遇到连续匹配问题先想清楚 dp 是不是“以结尾”定义再画二维表推一遍转移空间不够时优先考虑滚动数组但遍历方向一定要选对。这套思考方式不止对718有用做很多连续数组的题目都能少走弯路。