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:

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 的 长度。

更多

• 你的衣服我扒了 - 《最长公共子序列》

扩展

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

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

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