718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray

思路

方法一：暴力法

1 将A当作参考，枚举B中每一个元素，寻找A中是否存在相同元素2 存在，最长重复子数组长度+1，就判断下一个元素与A中相同元素的下一个元素是否相同，重复步骤2，3，不存在，记录此时最长重复子数组长度。

代码

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int ans = 0; for (int i = 0;i < A.size();i++){ for (int j = 0;j < B.size();j++){ int k = 0; while (A[i+k] == B[j+k]) k++; ans = max(ans,k); } } return ans; } };

很遗憾，超时了。

方法二：动态规划

参考官方题解。 按照我的理解，以元素本身开始的子数组。位于数组前面的元素理论上拥有比后面元素更长的重复子数组。例如以A[0]开始的重复子数组长度最长为5，而以A[4]为开始的重复子数组长度最长为1。所以本题可以采用从后向前转移的动态规划。 我们以一个二维数组来表示转移过程：（图解） 初始化： 大概示意图就是这样，是左上方传递，如果两个数相同，则两个元素指针都需要往前移，也就是斜上方。据此，我们可以推断出转移方程为：

dp[i][j]= A[I]==B[j]?dp[i+1][j+1]+1:0

代码：

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int n = A.size(), m = B.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); int ans = 0; for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0; ans = max(ans, dp[i][j]); } } return ans; } };

方法三：滑动窗口

参考链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray 评论区里有一位大佬@newhar写了简约写法，代码省去不少。 参考链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/