LeetCode-Go 题解718. Maximum Length of Repeated Subarray最长重复子数组动态规划与二分搜索 Rabin-Karp【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 第 718 题「Maximum Length of Repeated Subarray最长重复子数组」展开完整讲解题目约束、两种经典解法O(n²) 的动态规划与 O(n·log n) 的二分搜索 Rabin-Karp 滚动哈希并结合本仓库 leetcode/0718.Maximum-Length-of-Repeated-Subarray 中的 Go 实现与单元测试逐行拆解代码细节。读完本文你将同时掌握「子数组」类题目的 DP 状态设计方法以及用滚动哈希把 O(n²) 的字符串比较压缩到 O(n·log n) 的进阶技巧并学会如何验证两种解法在边界数据下的一致性。题目描述Given two integer arraysAandB, return the maximum length of an subarray that appears in both arrays. 给两个整数数组A和B返回两个数组中公共的、长度最长的子数组的长度。示例 1Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].注意数据范围1 len(A), len(B) 10000 A[i], B[i] 100需要特别强调两点语义题目要求的是子数组subarray即连续的一段元素而不是可跳跃匹配的「子序列subsequence」公共子数组只需出现在两个数组中的任意位置即可不需要起始下标一致。示例中[3, 2, 1]在A中对应下标 2、3、4在B中对应下标 0、1、2两个位置并不相同但长度 3 就是全局最长公共连续段[1,2,3]、[2,3,2]等都只在单边出现或长度更短。解法一动态规划DP状态定义与转移方程这是「最长公共子串连续子数组」类问题的标准 DP 解法本仓库实现为findLength1见 核心实现文件。定义dp[i][j]为A 数组中以下标i开始的子串与 B 数组中以下标j开始的子串其最长相同连续子串的长度。状态转移方程dp[i][j] dp[i1][j1] 1 (当 A[i] B[j])推导逻辑若A[i] B[j]那么这两个元素可以拼接到「从i1、j1开始的公共连续段」前面长度自然是在后续位置结果上加 1若A[i] ! B[j]则dp[i][j] 0无法从这个位置延伸出公共子数组。从状态转移方程可以看到dp[i][j]依赖dp[i1][j1]因此遍历顺序必须从后往前i、j均从len-1递减到 0这正是源码中两层循环都从尾部开始的原因。源码实现// 解法二 DP 动态规划 func findLength1(A []int, B []int) int { res, dp : 0, make([][]int, len(A)1) for i : range dp { dp[i] make([]int, len(B)1) } for i : len(A) - 1; i 0; i-- { for j : len(B) - 1; j 0; j-- { if A[i] B[j] { dp[i][j] dp[i1][j1] 1 if dp[i][j] res { res dp[i][j] } } } } return res }实现细节dp矩阵开成(len(A)1) x (len(B)1)多出的第len(A)行、第len(B)列默认全 0充当哨兵边界。当i或j走到数组末尾时dp[i1][j1]会自然读到 0从而避免显式的越界判断全局维护res记录遍历过程中出现的最大dp[i][j]因为最长公共子数组可能出现在矩阵中的任何位置而不仅仅是某个固定起点当A[i] ! B[j]时保持 0不做任何操作。复杂度分析时间复杂度O(n²)其中 n 为两个数组的长度题目约束均为 1000 量级1000×1000 的 DP 在可接受范围内空间复杂度O(n²)需要完整的二维 DP 表。解法二二分搜索 Rabin-Karp 滚动哈希思路来源把「比较字符串」变成「比较数字」DP 解法虽然直观但 O(n²) 的时间与空间在数据量更大时会成为瓶颈。本题仓库给出的最佳解法是二分搜索 Rabin-Karp见源码中findLength及配套的hashSlice、hasSamePrefix、hasRepeated。核心痛点在于判断两个长度为 L 的段是否相同朴素做法需要一重循环逐个比较字符耗时 O(L)。但如果能把一段数组映射成一个数字两个段是否相同就退化为两个整数是否相等单次比较变为 O(1)。这就是 Rabin-Karp 算法的核心思想把字符串/数组序列映射成数值用「数字比较」代替「逐字符比较」。码点进制与素数字符串映射成数字不能随意映射还要求能够利用已比较过的前缀动态推进、加速后续比较。Rabin-Karp 算法中有一个「码点进制」的概念类似于十进制中的进制基数一般取值为一个素数。本仓库源码直接复用了 Go 标准库strings包中的取值const primeRK 1677761916777619正是 Gostrings包内部hashStr所使用的 FNV 素数。选素数的好处是能显著降低哈希碰撞概率。此处不讨论 FNV 的完整原理只需理解它同时充当「进制」和「模数」h h*primeRK v构成了一个类似多项式求值的滚动哈希。滚动哈希的滑动窗口实现源码中的hashSlice负责把数组按固定窗口长度切成若干哈希值func hashSlice(arr []int, length int) []int { // hash 数组里面记录 arr 比 length 长出去部分的 hash 值 hash, pl, h : make([]int, len(arr)-length1), 1, 0 for i : 0; i length-1; i { pl * primeRK } for i, v : range arr { h h*primeRK v if i length-1 { hash[i-length1] h h - pl * arr[i-length1] } } return hash }逐行拆解输出数组长度为len(arr)-length1即所有长度为length的窗口数量先预计算pl primeRK^(length-1)用于后续滑动窗口时减掉最左侧元素对哈希的贡献主循环对每个元素执行h h*primeRK v相当于把新元素追加到多项式末尾当窗口已满i length-1把当前h记录到结果数组然后执行h - pl * arr[i-length1]pl * arr[i-length1]正是即将滑出窗口的最左元素所贡献的权重减掉它后h天然变成了「右移一个位置」后的新窗口哈希。整个过程每个元素只进出一次摊还 O(1)总复杂度 O(n)代码注释中「hash 数组里面记录 arr 比 length 长出去部分的 hash 值」指的就是这个滑动过程中维护的窗口哈希序列。哈希碰撞的兜底校验哈希相等只能说明「大概率」相同不能完全排除碰撞。源码用hasSamePrefix做最终确认func hasSamePrefix(A, B []int, length int) bool { for i : 0; i length; i { if A[i] ! B[i] { return false } } return true }即当两个窗口哈希值一致时再逐元素比较一次确认两段确实完全相同杜绝假阳性。这也是 Rabin-Karp 匹配的标准做法——哈希用于快速筛除不匹配项命中后用朴素比较兜底。二分搜索最长长度因为「是否存在长度为 L 的公共子数组」具有单调性——若存在长度为 L 的公共子数组则对任意更短的L L也一定存在截取前L个元素即可——所以可以直接对答案长度做二分。仓库实现// 解法一 二分搜索 Rabin-Karp func findLength(A []int, B []int) int { low, high : 0, min(len(A), len(B)) for low high { mid : (low high 1) 1 if hasRepeated(A, B, mid) { low mid } else { high mid - 1 } } return low }二分上界为min(len(A), len(B))公共子数组不可能超过较短数组的长度下界为 0采用mid (low high 1) 1的上取整写法配合low mid的移动方式避免死循环hasRepeated(A, B, mid)负责判定「长度为 mid 的公共子数组是否存在」。hasRepeated的实现把两个关键步骤串了起来func hasRepeated(A, B []int, length int) bool { hs : hashSlice(A, length) hashToOffset : make(map[int][]int, len(hs)) for i, h : range hs { hashToOffset[h] append(hashToOffset[h], i) } for i, h : range hashSlice(B, length) { if offsets, ok : hashToOffset[h]; ok { for _, offset : range offsets { if hasSamePrefix(A[offset:], B[i:], length) { return true } } } } return false }逻辑梳理对A的所有长度为length的窗口求哈希建立hash - 起始下标列表的映射map[int][]int同哈希的多个窗口都要记录下来防止漏配对B的每个窗口求哈希若该哈希出现在映射中则枚举A中对应下标的窗口用hasSamePrefix做元素级比对一旦找到真正相同的两段立即返回trueB全部遍历完仍无命中则返回false。整体复杂度每次hasRepeated判定需要 O(n) 时间两次hashSlice各 O(n)map 查找均摊 O(1)二分最多进行 O(log n) 轮因此整体时间复杂度O(n·log n)空间复杂度O(n)哈希数组与 map 均为线性大小相比 DP 的 O(n²) 在时间与空间上都有质的提升。两种解法的对比与选择维度动态规划findLength1二分 Rabin-KarpfindLength时间复杂度O(n²)O(n·log n)空间复杂度O(n²)O(n)实现难度低状态定义直观中需理解滚动哈希与碰撞兜底适用场景数据规模小、追求简洁可读数据规模大、追求性能上限在本仓库的测试中两种实现针对同一组测试用例输出完全一致可作为「以朴素 DP 校验高级算法正确性」的交叉验证范例。测试用例与验证仓库为本题编写了 5 组测试用例见 测试文件覆盖了典型、边界与碰撞场景输入 A输入 B期望输出覆盖意图[0,0,0,0,0][0,0,0,0,0]5两数组完全相同答案是整个数组长度[1,2,3,2,1][3,2,1,4,7]3题目原始示例[0,0,0,0,1][1,0,0,0,0]4公共子数组出现在两数组的不同位置长度为 100 的构造数组长度为 100 的构造数组59大输入下的正确性[1,0,99,99][0,16777619,99]1刻意构造的哈希碰撞用例其中最后一组用例非常巧妙A中长度为 2 的窗口[1,0]与B中的[0,16777619]在 base 16777619 下哈希相同1*16777619 0 0*16777619 16777619但实际内容不同正好迫使hasSamePrefix走到「哈希一致但元素不匹配」的分支验证碰撞兜底逻辑确实生效同时len(A) len(B)也覆盖了min函数返回b的分支。最终期望答案 1[99]出现在两数组末尾。测试函数对每组用例同时调用两种解法并分别断言got : findLength(p.A, p.B) if got ! a.one { t.Fatalf(findLength(%v, %v) %v, want %v, p.A, p.B, got, a.one) } if got1 : findLength1(p.A, p.B); got1 ! a.one { t.Fatalf(findLength1(%v, %v) %v, want %v, p.A, p.B, got1, a.one) }需要运行验证时在仓库根目录执行go test -v ./leetcode/0718.Maximum-Length-of-Repeated-Subarray/测试名称为Test_Problem718运行后可同时确认二分 Rabin-Karp 与 DP 两种实现均通过全部用例。总结LeetCode 718 是「最长公共子串」类问题的代表性题目也是一道非常合适的进阶训练题DP 解法给出了标准的 O(n²) 状态设计与从后向前的遍历顺序是此类问题必须掌握的基础功二分 Rabin-Karp 解法展示了如何用「长度单调性」把最优化问题转化为判定问题再用滚动哈希把「段比较」降为 O(1)最终把整体复杂度优化到 O(n·log n)仓库源码中的primeRK 16777619与 Go 标准库strings包保持一致配合hashSlice的窗口滑动公式和hasSamePrefix的碰撞兜底构成了一套完整、可直接复用的滚动哈希模板。如果后续遇到「最长重复子串」「重复 DNA 序列」等基于相同子串判定的题目都可以直接迁移本节的滚动哈希 二分框架。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：718. Maximum Length of Repeated Subarray（最长重复子数组，动态规划与二分搜索 + Rabin-Karp）
LeetCode-Go 题解718. Maximum Length of Repeated Subarray最长重复子数组动态规划与二分搜索 Rabin-Karp【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 第 718 题「Maximum Length of Repeated Subarray最长重复子数组」展开完整讲解题目约束、两种经典解法O(n²) 的动态规划与 O(n·log n) 的二分搜索 Rabin-Karp 滚动哈希并结合本仓库 leetcode/0718.Maximum-Length-of-Repeated-Subarray 中的 Go 实现与单元测试逐行拆解代码细节。读完本文你将同时掌握「子数组」类题目的 DP 状态设计方法以及用滚动哈希把 O(n²) 的字符串比较压缩到 O(n·log n) 的进阶技巧并学会如何验证两种解法在边界数据下的一致性。题目描述Given two integer arraysAandB, return the maximum length of an subarray that appears in both arrays. 给两个整数数组A和B返回两个数组中公共的、长度最长的子数组的长度。示例 1Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].注意数据范围1 len(A), len(B) 10000 A[i], B[i] 100需要特别强调两点语义题目要求的是子数组subarray即连续的一段元素而不是可跳跃匹配的「子序列subsequence」公共子数组只需出现在两个数组中的任意位置即可不需要起始下标一致。示例中[3, 2, 1]在A中对应下标 2、3、4在B中对应下标 0、1、2两个位置并不相同但长度 3 就是全局最长公共连续段[1,2,3]、[2,3,2]等都只在单边出现或长度更短。解法一动态规划DP状态定义与转移方程这是「最长公共子串连续子数组」类问题的标准 DP 解法本仓库实现为findLength1见 核心实现文件。定义dp[i][j]为A 数组中以下标i开始的子串与 B 数组中以下标j开始的子串其最长相同连续子串的长度。状态转移方程dp[i][j] dp[i1][j1] 1 (当 A[i] B[j])推导逻辑若A[i] B[j]那么这两个元素可以拼接到「从i1、j1开始的公共连续段」前面长度自然是在后续位置结果上加 1若A[i] ! B[j]则dp[i][j] 0无法从这个位置延伸出公共子数组。从状态转移方程可以看到dp[i][j]依赖dp[i1][j1]因此遍历顺序必须从后往前i、j均从len-1递减到 0这正是源码中两层循环都从尾部开始的原因。源码实现// 解法二 DP 动态规划 func findLength1(A []int, B []int) int { res, dp : 0, make([][]int, len(A)1) for i : range dp { dp[i] make([]int, len(B)1) } for i : len(A) - 1; i 0; i-- { for j : len(B) - 1; j 0; j-- { if A[i] B[j] { dp[i][j] dp[i1][j1] 1 if dp[i][j] res { res dp[i][j] } } } } return res }实现细节dp矩阵开成(len(A)1) x (len(B)1)多出的第len(A)行、第len(B)列默认全 0充当哨兵边界。当i或j走到数组末尾时dp[i1][j1]会自然读到 0从而避免显式的越界判断全局维护res记录遍历过程中出现的最大dp[i][j]因为最长公共子数组可能出现在矩阵中的任何位置而不仅仅是某个固定起点当A[i] ! B[j]时保持 0不做任何操作。复杂度分析时间复杂度O(n²)其中 n 为两个数组的长度题目约束均为 1000 量级1000×1000 的 DP 在可接受范围内空间复杂度O(n²)需要完整的二维 DP 表。解法二二分搜索 Rabin-Karp 滚动哈希思路来源把「比较字符串」变成「比较数字」DP 解法虽然直观但 O(n²) 的时间与空间在数据量更大时会成为瓶颈。本题仓库给出的最佳解法是二分搜索 Rabin-Karp见源码中findLength及配套的hashSlice、hasSamePrefix、hasRepeated。核心痛点在于判断两个长度为 L 的段是否相同朴素做法需要一重循环逐个比较字符耗时 O(L)。但如果能把一段数组映射成一个数字两个段是否相同就退化为两个整数是否相等单次比较变为 O(1)。这就是 Rabin-Karp 算法的核心思想把字符串/数组序列映射成数值用「数字比较」代替「逐字符比较」。码点进制与素数字符串映射成数字不能随意映射还要求能够利用已比较过的前缀动态推进、加速后续比较。Rabin-Karp 算法中有一个「码点进制」的概念类似于十进制中的进制基数一般取值为一个素数。本仓库源码直接复用了 Go 标准库strings包中的取值const primeRK 1677761916777619正是 Gostrings包内部hashStr所使用的 FNV 素数。选素数的好处是能显著降低哈希碰撞概率。此处不讨论 FNV 的完整原理只需理解它同时充当「进制」和「模数」h h*primeRK v构成了一个类似多项式求值的滚动哈希。滚动哈希的滑动窗口实现源码中的hashSlice负责把数组按固定窗口长度切成若干哈希值func hashSlice(arr []int, length int) []int { // hash 数组里面记录 arr 比 length 长出去部分的 hash 值 hash, pl, h : make([]int, len(arr)-length1), 1, 0 for i : 0; i length-1; i { pl * primeRK } for i, v : range arr { h h*primeRK v if i length-1 { hash[i-length1] h h - pl * arr[i-length1] } } return hash }逐行拆解输出数组长度为len(arr)-length1即所有长度为length的窗口数量先预计算pl primeRK^(length-1)用于后续滑动窗口时减掉最左侧元素对哈希的贡献主循环对每个元素执行h h*primeRK v相当于把新元素追加到多项式末尾当窗口已满i length-1把当前h记录到结果数组然后执行h - pl * arr[i-length1]pl * arr[i-length1]正是即将滑出窗口的最左元素所贡献的权重减掉它后h天然变成了「右移一个位置」后的新窗口哈希。整个过程每个元素只进出一次摊还 O(1)总复杂度 O(n)代码注释中「hash 数组里面记录 arr 比 length 长出去部分的 hash 值」指的就是这个滑动过程中维护的窗口哈希序列。哈希碰撞的兜底校验哈希相等只能说明「大概率」相同不能完全排除碰撞。源码用hasSamePrefix做最终确认func hasSamePrefix(A, B []int, length int) bool { for i : 0; i length; i { if A[i] ! B[i] { return false } } return true }即当两个窗口哈希值一致时再逐元素比较一次确认两段确实完全相同杜绝假阳性。这也是 Rabin-Karp 匹配的标准做法——哈希用于快速筛除不匹配项命中后用朴素比较兜底。二分搜索最长长度因为「是否存在长度为 L 的公共子数组」具有单调性——若存在长度为 L 的公共子数组则对任意更短的L L也一定存在截取前L个元素即可——所以可以直接对答案长度做二分。仓库实现// 解法一 二分搜索 Rabin-Karp func findLength(A []int, B []int) int { low, high : 0, min(len(A), len(B)) for low high { mid : (low high 1) 1 if hasRepeated(A, B, mid) { low mid } else { high mid - 1 } } return low }二分上界为min(len(A), len(B))公共子数组不可能超过较短数组的长度下界为 0采用mid (low high 1) 1的上取整写法配合low mid的移动方式避免死循环hasRepeated(A, B, mid)负责判定「长度为 mid 的公共子数组是否存在」。hasRepeated的实现把两个关键步骤串了起来func hasRepeated(A, B []int, length int) bool { hs : hashSlice(A, length) hashToOffset : make(map[int][]int, len(hs)) for i, h : range hs { hashToOffset[h] append(hashToOffset[h], i) } for i, h : range hashSlice(B, length) { if offsets, ok : hashToOffset[h]; ok { for _, offset : range offsets { if hasSamePrefix(A[offset:], B[i:], length) { return true } } } } return false }逻辑梳理对A的所有长度为length的窗口求哈希建立hash - 起始下标列表的映射map[int][]int同哈希的多个窗口都要记录下来防止漏配对B的每个窗口求哈希若该哈希出现在映射中则枚举A中对应下标的窗口用hasSamePrefix做元素级比对一旦找到真正相同的两段立即返回trueB全部遍历完仍无命中则返回false。整体复杂度每次hasRepeated判定需要 O(n) 时间两次hashSlice各 O(n)map 查找均摊 O(1)二分最多进行 O(log n) 轮因此整体时间复杂度O(n·log n)空间复杂度O(n)哈希数组与 map 均为线性大小相比 DP 的 O(n²) 在时间与空间上都有质的提升。两种解法的对比与选择维度动态规划findLength1二分 Rabin-KarpfindLength时间复杂度O(n²)O(n·log n)空间复杂度O(n²)O(n)实现难度低状态定义直观中需理解滚动哈希与碰撞兜底适用场景数据规模小、追求简洁可读数据规模大、追求性能上限在本仓库的测试中两种实现针对同一组测试用例输出完全一致可作为「以朴素 DP 校验高级算法正确性」的交叉验证范例。测试用例与验证仓库为本题编写了 5 组测试用例见 测试文件覆盖了典型、边界与碰撞场景输入 A输入 B期望输出覆盖意图[0,0,0,0,0][0,0,0,0,0]5两数组完全相同答案是整个数组长度[1,2,3,2,1][3,2,1,4,7]3题目原始示例[0,0,0,0,1][1,0,0,0,0]4公共子数组出现在两数组的不同位置长度为 100 的构造数组长度为 100 的构造数组59大输入下的正确性[1,0,99,99][0,16777619,99]1刻意构造的哈希碰撞用例其中最后一组用例非常巧妙A中长度为 2 的窗口[1,0]与B中的[0,16777619]在 base 16777619 下哈希相同1*16777619 0 0*16777619 16777619但实际内容不同正好迫使hasSamePrefix走到「哈希一致但元素不匹配」的分支验证碰撞兜底逻辑确实生效同时len(A) len(B)也覆盖了min函数返回b的分支。最终期望答案 1[99]出现在两数组末尾。测试函数对每组用例同时调用两种解法并分别断言got : findLength(p.A, p.B) if got ! a.one { t.Fatalf(findLength(%v, %v) %v, want %v, p.A, p.B, got, a.one) } if got1 : findLength1(p.A, p.B); got1 ! a.one { t.Fatalf(findLength1(%v, %v) %v, want %v, p.A, p.B, got1, a.one) }需要运行验证时在仓库根目录执行go test -v ./leetcode/0718.Maximum-Length-of-Repeated-Subarray/测试名称为Test_Problem718运行后可同时确认二分 Rabin-Karp 与 DP 两种实现均通过全部用例。总结LeetCode 718 是「最长公共子串」类问题的代表性题目也是一道非常合适的进阶训练题DP 解法给出了标准的 O(n²) 状态设计与从后向前的遍历顺序是此类问题必须掌握的基础功二分 Rabin-Karp 解法展示了如何用「长度单调性」把最优化问题转化为判定问题再用滚动哈希把「段比较」降为 O(1)最终把整体复杂度优化到 O(n·log n)仓库源码中的primeRK 16777619与 Go 标准库strings包保持一致配合hashSlice的窗口滑动公式和hasSamePrefix的碰撞兜底构成了一套完整、可直接复用的滚动哈希模板。如果后续遇到「最长重复子串」「重复 DNA 序列」等基于相同子串判定的题目都可以直接迁移本节的滚动哈希 二分框架。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
