题目来源：力扣（LeetCode）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) <= 10000 <= A[i], B[i] < 100开始之前，先分析下题目。题目中要求计算两个数组的最长公共子数组。从示例中可以看到，子数组要在原数组中连续。那么，我们可以使用暴力的解法尝试逐个比较，示例代码大致如下:
class Solution: def findLength(self, A: List[int], B: List[int]) -> int: ans = 0 for i in range(len(A)): for j in range(len(B)): length = 0 while i+length < len(A) and j + length < len(B) and A[i+length] == B[j+length]: length+=1 ans = max(ans, length) return ans大致说下执行的流程，这段代码中，先枚举数组 A 和 数组 B 的起始位置，然后逐个比较元素是否相同计算最长公共前缀长度 length，循环执行直至结束。维护 length，取最大值就是所求答案。
但是执行这段代码会超时，因为这段代码的时间复杂度最快的情况下是 O(n^3)。但是我们可以根据暴力解的思路进行优化。
思路：动态规划
上面已经说明，最坏的情况下，时间复杂度为 O(n^3)。这是因为最坏的情况下，对于任意的 i，j，A[i] 和 B[j] 比较的次数为 min(i+1,j+1)。现在来验证这种情况，假设有以下数组 A 和 数组 B：
A = [0, 0, 0, 0] B = [0, 0, 0, 0]假设 i，j 都等于 3，那么在暴力解代码中 A[3] 和 B[3] 会被比较 4 次。因为当 (i，j) 为 (0, 0),(1, 1),(2, 2),(3, 3) 的时候，在 while 语句都会判断一次。
那么优化的思路就从这里进行考虑，使得任意 A[i] 和 B[j] 只需要比较一次。
也就是说，当确定 A[i] == B[j] 的情况下，A[i:] 和 B[j:] 的公共前缀长度会等于 A[i+1:] 和 B[j+1:] 的公共前缀长度加 1。否则的话，A[i:] 和 B[j:] 的公共前缀长度为 0。（因为要求子数组连续，此时首元素不相等）
那么我们假设，dp[i][j] 表示 A[i:] 和 B[j:] 的公共前缀长度，根据上面的分析可以得到：
当 A[i]==B[j] 时，那么 dp[i][j] = dp[i+1][j+1] + 1，否则 dp[i][j] = 0。
求得所有的 dp[i][j]，其中最大的就是要求的答案。
由于 dp[i][j] 是由 dp[i+1][j+1] 得到的，那么遍历数组的时候，从右往左遍历求解。
具体的实现代码见【代码实现 # 动态规划】。
思路：滑动窗口
这道题还可以使用滑动窗口的方法。在前面的方法可以看到，需要进行多次比较之后才开始计算公共前缀。这是因为重复子数组在两个原数组中的起始位置有可能不一样。
如果知道起始位置的话，那么从当前位置开始遍历，就可以计算出最长公共的子数组长度。
那么这里的问题就是如何知道相应的起始位置并对齐。这里分为两种情况：
固定数组 A，移动数组 B，使得 B 的首元素与数组 A 某个元素对齐，找到起始位置，计算长度；固定数组 B，移动数组 A，使得 A 的首元素与数组 B 某个元素对齐，找到起始位置，计算长度。以示例 1 为例：
输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。具体实现的过程如下图：
具体实现代码见【代码实现 # 滑动窗口】
实现结果 | 动态规划
实现结果 | 滑动窗口
文章原创，欢迎关注点赞。微信公众号《书所集录》同步更新，同样欢迎关注。
