# 0718. 最长重复子数组

### 题目地址（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
```

### 前置知识

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

### 公司

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

### 思路

关于这个类型， 我专门写了一个专题《你的衣服我扒了 - 《最长公共子序列》》，里面讲了三道题，其中就有这个。

这就是最经典的最长公共子序列问题。一般这种求解**两个数组或者字符串求最大或者最小**的题目都可以考虑动态规划，并且通常都定义 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://p.ipic.vip/2h3f8q.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/718.maximum-length-of-repeated-subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.