0718. 最长重复子数组 · ttttt

# 0718. 最长重复子数组 ## 题目地址（718. 最长重复子数组） <https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/> ## 题目描述 ``` <pre class="calibre18">``` 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。示例 1: 输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。说明: 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100 ``` ``` ## 前置知识 - 哈希表 - 数组 - 二分查找 - 动态规划 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路这就是最经典的最长公共子序列问题。一般这种求解**两个数组或者字符串求最大或者最小**的题目都可以考虑动态规划，并且通常都定义 dp\[i\]\[j\] 为 `以 A[i], B[j] 结尾的 xxx`。这道题就是：`以 A[i], B[j] 结尾的两个数组中公共的、长度最长的子数组的长度`。算法很简单： - 双层循环找出所有的 i, j 组合，时间复杂度 O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 - 如果 A\[i\] == B\[j\]，dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1 - 否则，dp\[i\]\[j\] = 0 - 循环过程记录最大值即可。 ## 关键点解析 - dp 建模套路 ## 代码代码支持：Python Python Code: ``` <pre class="calibre18">``` class Solution: def findLength(self, A, B): m, n = len(A), len(B) ans = 0 dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] 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(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 - 空间复杂度：O(m∗n)O(m \* n)O(m∗n)，其中 m 和 n 分别为 A 和 B 的长度。 ## 更多 - [你的衣服我扒了 - 《最长公共子序列》](https://lucifer.ren/blog/2020/07/01/LCS/) ## 扩展二分查找也是可以的，不过并不容易想到，大家可以试试。更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)