## 题目地址（718. 最长重复子数组）

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

## 题目描述

```
给两个整数数组  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
```

## 前置知识

- 哈希表
- 数组
- 二分查找
- 动态规划

## 公司

- 阿里
- 腾讯
- 百度
- 字节

## 思路

关于这个类型， 我专门写了一个专题《你的衣服我扒了 - 《最长公共子序列》》[](https://lucifer.ren/blog/2020/07/01/LCS/)，里面讲了三道题，其中就有这个。

这就是最经典的最长公共子序列问题。一般这种求解**两个数组或者字符串求最大或者最小**的题目都可以考虑动态规划，并且通常都定义 dp[i][j] 为 `以 A[i], B[j] 结尾的 xxx`。这道题就是：`以 A[i], B[j] 结尾的两个数组中公共的、长度最长的子数组的长度`。 算法很简单：

- 双层循环找出所有的 i, j 组合，时间复杂度 $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:

```py
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)$，其中 m 和 n 分别为 A 和 B 的 长度。
- 空间复杂度：$O(m * n)$，其中 m 和 n 分别为 A 和 B 的 长度。

## 更多

- [你的衣服我扒了 - 《最长公共子序列》](https://lucifer.ren/blog/2020/07/01/LCS/)

## 扩展

二分查找也是可以的，不过并不容易想到，大家可以试试。

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu0yircgj30p00dwt9t.jpg)
