leetcode 718 最长重复子数组这道题我看到它在很多公司的算法面试里都出现过题目本身不长但解法之间的差距能看出一个人对连续这个概念的理解深度。最常见的做法是动态规划填一张二维表几分钟就能写完代价却是 O(n*m) 的空间而滑动窗口解法能把空间压到 O(1)思路还非常直观。这篇文章不打算把每种解法都堆一遍就专注把滑动窗口这一个解法讲透它到底在滑什么、为什么要双向对齐、代码怎么写才不漏边界以及面试时怎么把这个解法讲得让人信服。无论你是刷题冲刺还是准备面试接下来这些内容应该能帮你省下不少自己踩坑的时间。1. 先搞清楚题目到底在问什么1.1 题目描述与输出要求题目原文很短给定两个整数数组 nums1 和 nums2返回两个数组中公共的、长度最长的子数组的长度。官方示例是 nums1 [1,2,3,2,1]nums2 [3,2,1,4,7]最长公共子数组是 [3,2,1]所以答案是 3。这里第一个要理解透的词是子数组。子数组要求连续从数组里挑一段段内元素在原数组里必须是紧挨着的。它和子序列是两个概念子序列允许中间跳着取。一个常用来区分的例子nums1 [1,2,3]nums2 [3,1,2]。这两个数组的最长公共子序列是 [1,2]长度 2但最长公共子数组只有 1因为你找不到一个在两个数组里都连续出现、长度能超过 1 的片段。如果面试时直接拿最长公共子序列的状态转移来套这道题大概率会翻车。1.2 别忽视重复值带来的干扰这道题的数据范围是数组长度最大 1000元素取值在 0 到 100 之间重复值非常常见。比如 nums1 [1,1,1,1]nums2 [1,1]答案是 2不是 1 也不是 4。直觉上的坑在于nums1 里确实有 4 个 1但两个数组的公共连续片段最长只能到 2因为短数组一共只有 2 个元素。重复值意味着我们不能用元素唯一配对的思路也不能先排序再上双指针因为排序会破坏数组的相对顺序。只能老老实实按位置对齐、按顺序逐位比较。滑动窗口解法对重复值很友好因为它的比较发生在固定对齐状态下同一个值出现在不同位置会被分到不同的对齐状态里互不干扰不需要额外的去重逻辑。1.3 这道题到底在考什么能力这道题在面试里被高频使用核心不是考你 DP 公式背得熟不熟而是考两件事第一你能不能准确区分连续子数组和非连续子序列第二你能不能把一个二维问题用更省空间的思路重新组织。这两件事在真实工程里都有对应场景比如日志系统里找连续重复的错误序列、文本比对工具里做版本相似度分析底层都是类似的连续匹配模型。所以不要只把它当成一道刷题模板理解透了对解决实际问题也有帮助。2. 滑动窗口解法的核心思路两条纸带的相对位移2.1 把两个数组想象成两条纸带我第一次理解滑动窗口解法靠的是一个特别朴素的想法把 nums1 和 nums2 分别写在两条长纸带上上下对齐放着然后让其中一条左右滑动。每次停下来就从上到下逐格检查上下对应的数字是否相等。连续相等的那些格子就对应两个数组的一个公共子数组。所有滑动位置里最长的一段连续相等长度就是答案。这个比喻真的不是辅助理解的花架子它就是滑动窗口解法的本体。两个数组之间不存在绝对对齐只存在相对偏移量。nums1 的第 0 个元素可以和 nums2 的第 0 个元素对齐也可以和 nums2 的第 3 个元素对齐。每确定一个偏移量就等价于确定了一种上下摆放的位置关系。2.2 偏移量枚举两个方向一个都不能少假设 nums1 长度 nnums2 长度 m。把所有可能的对齐状态分成两类第一类nums1 的第 i 个元素与 nums2 的第 0 个元素对齐i 从 0 到 n-1。这时公共重叠区从 nums1[i] 开始能比较的格子数是 min(m, n - i)。第二类nums2 的第 j 个元素与 nums1 的第 0 个元素对齐j 从 0 到 m-1。这时公共重叠区从 nums2[j] 开始能比较的格子数是 min(n, m - j)。为什么两个方向都要因为任意一个公共子数组它在 nums1 里的起始位置是 p在 nums2 里的起始位置是 q。如果 p q说明它在 nums1 里起步更晚把 nums1 的第 p-q 个元素和 nums2 的第 0 个元素对齐就能让两个起始位置上下重合如果 p q则反过来把 nums2 的第 q-p 个元素和 nums1 的第 0 个元素对齐。所以两个方向合起来才覆盖了所有可能的公共子数组。只写一个方向的代码是这道题最经典的 bug没有之一。我见过不少实现跑出来的答案不对排查半天发现就是漏了第二类对齐。画两条纸带的图这个问题一眼就能看出来。2.3 窗口宽度固定不是那种伸缩窗口这里要特别提醒这道题的滑动窗口和你刷题时常说的双指针维护可变区间不是一回事。后者典型如 leetcode 209 最短子数组之和右指针扩张、左指针收缩窗口长度一直在变。而在 718 里每个对齐状态下重叠区的宽度是固定的窗口本身不伸缩我们做的其实是整体位移加线性扫描。在每个对齐状态下我们维护一个变量 cur表示当前连续相等的长度。从左到右扫过重叠区上下两个数相等cur 加 1一旦不等cur 立刻归零因为公共子数组必须连续断了就断了一切重来。这个遇不等就清零的逻辑正是子数组和子序列在代码层面的分水岭也是这道题和 1143 最长公共子序列最核心的区别。3. 完整代码实现与关键细节解析3.1 可以直接跑的 Python 实现from typing import List class Solution: def findLength(self, nums1: List[int], nums2: List[int]) - int: n, m len(nums1), len(nums2) ans 0 # 方向一nums1 从位置 i 开始与 nums2[0] 对齐 for i in range(n): length min(m, n - i) ans max(ans, self._max_common(nums1, nums2, i, 0, length)) # 方向二nums2 从位置 j 开始与 nums1[0] 对齐 # 从 1 开始是为了跳过与上面 i0 重复的对齐状态 for j in range(1, m): length min(n, m - j) ans max(ans, self._max_common(nums1, nums2, 0, j, length)) return ans def _max_common(self, A: List[int], B: List[int], startA: int, startB: int, length: int) - int: cur 0 # 当前连续相等的子数组长度 best 0 # 当前对齐状态下扫到的最长值 for k in range(length): if A[startA k] B[startB k]: cur 1 if cur best: best cur else: cur 0 return best3.2 几个容易写错的设计点第一length 的计算。方向一里i 越往后nums1 剩余可比较的元素越少重叠区宽度要么是 m要么是 n - i取较小值。很多初学者写成 min(m, n)数组一长一短就会越界或者算错长度。第二第二层循环从 j 1 开始。如果从 j 0 开始并不会让答案出错因为 i 0 和 j 0 对应同一种对齐状态nums1[0] 对齐 nums2[0]最多是重复扫一遍浪费一点时间。但从 1 开始代码更干净也方便在面试时解释每个对齐状态只算一次。第三_max_common 里遇到不等时应该 cur 0 而不是 break。一段匹配结束之后后面可能还有新的一段。比如 nums1 [1,2,1,2]nums2 [1,2,1,2]在某个偏移下会出现两段独立的匹配必须把每段分别数清楚再取最大值。break 会让 cur 停在第一段或者干脆得到 0这是第二个经典翻车点。提示写完代码先拿官方示例跑一遍再跑一遍全相等的用例例如 [1,2,3,4,5] 和 [1,2,3,4,5]。全相等用例如果输出不是 5多半就是 length 或者对齐方向出了问题。3.3 复杂度总比较次数恰好是 n*m很多人误以为滑动窗口是 O(n m)其实不对。每个对齐状态都要扫一遍重叠区把每个状态的扫描格子数加起来结果恰好是 n*m。我随手举个例子。n 5m 3。方向一的扫描长度分别是 min(3,5)3min(3,4)3min(3,3)3min(3,2)2min(3,1)1合计 12方向二的扫描长度是 min(5,2)2 和 min(5,1)1合计 3总共 15正好等于 5*3。这不是巧合。两个数组一共构成 nm 个下标对 (a, b)a 是 nums1 的下标b 是 nums2 的下标。任意一个下标对都存在唯一一个对齐状态让 nums1[a] 和 nums2[b] 上下重合这个对齐状态的偏移量就是 a - b。所以每个下标对恰好被比较一次总比较次数必然是 nm。结论时间复杂度 O(n*m)额外空间 O(1)。在这个数据范围下n*m 最多是 10^6 次比较Python 跑起来完全没有压力。所以这道题用滑动窗口在时间和空间两点上都站得住。3.4 它和动态规划其实是同一件事如果面试官追问这个解法和 DP 是什么关系可以这样答滑动窗口本质上就是沿着 DP 矩阵的对角线递推。设 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度那么状态转移是 dp[i][j] dp[i-1][j-1] 1两个数相等不等则为 0。注意 dp[i][j] 只依赖左上角的 dp[i-1][j-1]也就是说同一条对角线上的 dp 值可以沿着对角线方向一个个推出来。滑动窗口里的 cur其实就是当前对角线上一格的 dp 值。每个对齐状态下从头扫到尾等价于把一条对角线的 dp 全部算完然后立刻扔掉。二维 DP 按行填表需要一整张表滚动数组优化后也还要一个一维数组滑动窗口连这一步都省了只保留 cur 一个变量。把这层关系讲出来面试官基本就知道你是真的理解了而不是背了一个模板。4. 边界条件、解法对比与面试实战手册4.1 最容易翻车的边界场景场景示例预期结果注意点完全没有公共元素[1,2,3] 与 [4,5,6]0cur 一直为 0ans 初始值要正确处理数组完全相等[1,2,3] 与 [1,2,3]3答案受限于较短的数组长度只有单个元素相等[1,2,3] 与 [4,2,5]1别把不连续的片段拼起来重复元素连续段[1,1,1,1] 与 [1,1]2答案不会超过 min(n, m)一长一短长度 1000 与长度 10 或 1length 算错会导致越界自测的时候我强烈建议写一个暴力解法做对拍。暴力解就是三层循环枚举 nums1 的起点枚举 nums2 的起点然后逐位往后对比直到不等记录最长长度。写起来很简单def brute_force(a, b): ans 0 n, m len(a), len(b) for i in range(n): for j in range(m): k 0 while i k n and j k m and a[i k] b[j k]: k 1 ans max(ans, k) return ans然后生成随机数组把滑动窗口的结果和暴力结果比对几百轮不一致就说明实现有问题。这个习惯能帮你少掉很多头发。4.2 主流解法横向对比解法时间复杂度空间复杂度代码量亮点暴力枚举O(nmmin(n,m))O(1)很少只用来对拍验证正确性动态规划O(n*m)O(n*m)可压到 O(m)少思路最直接方便回溯具体子数组滑动窗口O(n*m)O(1)少空间最优几何直觉强二分滚动哈希O((nm)log(min(n,m)))O(nm)多大数组更快但有哈希碰撞风险实际面试里我建议这样组织答案先给暴力解确认题目理解没有偏差再上二维 DP 作为baseline最后补一句如果希望空间降到 O(1)这道题有一个滑动窗口做法然后引出纸带比喻。一层层递进比一上来就甩出滑动窗口代码好得多也给了面试官一个完整的思维梯度。4.3 面试追问怎么接面试官常见的追问方向有三个。第一能不能优化空间直接把滑动窗口讲清楚重点强调 cur 只保留当前对齐状态的连续匹配长度完全不需要二维存储。第二这道题和最长公共子序列有什么区别从连续性和转移方程入手子序列是取 max 跳过当前字符子数组是断了就清零连续性决定了状态转移的方式。第三如果数组特别长怎么办可以提二分答案加滚动哈希的进阶思路先猜一个公共长度 L用哈希把所有长度为 L 的子数组指纹算出来检查两个数组有没有交集再二分 L。这个方案把时间降到 O((nm)log(min(n,m)))但要处理哈希冲突一般用双哈希或者 64 位哈希来降低概率。这个属于加分项讲不清楚宁可不说别硬撑。5. 一点实操体会最后分享几个我自己踩过的坑。第一次写这道题的滑动窗口时我只写了方向一以为把 nums1 从头到尾滑动一遍就够了结果有一半的公共子数组压根扫不到调了半天才发现漏了方向二。后来在纸上画了两条纸带才真正理解对齐这件事。第二次犯的错是在 _max_common 里遇到不等直接 break导致如果最长公共段不在开头答案就被截断了正确的做法是清零后继续往后找。现在我的固定流程是先写暴力解对拍再用小数组手动走一遍流程最后才提交。这道题想在面试里稳稳拿下把纸带和对角线 DP这两个概念讲顺基本就没什么问题了。