leetcode718. 最长重复子数组动态规划，滑动窗口

文章目录

题目：leetcode718. 最长重复子数组/动态规划基本思想1：动态规划基本思想2：滑动窗口基本思想3：暴力

题目：leetcode718. 最长重复子数组/动态规划

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思想1：动态规划

dp[i][j]：以 A[i - 1]结束的子数组 和 B[j - 1]结束的子数组的最长匹配的个数，因为这里是子数组每个元素要连续（区别：子序列，子序列不连续）状态：两个数组中的每一个字符选择：是否包含当前元素状态转移方程：当前两个元素相等，dp[i][j] = 1 + dp[i - 1][j - 1]；不相等：dp[i][j] = dp[i - 1][j - 1]

说明：如果是最长子序列，dp数组的含义和状态转移方程均不一样

dp[i][j]：A的前 i 个字符和B的前 j 个字符最长匹配的子序列状态转移方程：$$dp[i][j]=max(dp[i-1][j-1]+(A[i-1]==B[j-1]?1:0),dp[i-1][j],dp[i][j-1])$$

时间复杂度：O（N * M）

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { //动态规划 vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0)); int res = 0; for(int i = 1; i <= A.size(); ++i){ for(int j = 1; j <= B.size(); ++j){ if(A[i - 1] == B[j - 1]){ dp[i][j] = dp[i - 1][j - 1] + 1; } res = max(res, dp[i][j]); //cout << dp[i][j] << " "; } //cout << endl; } return res; } };

基本思想2：滑动窗口

该思想是基于：最长子数组在两个数组中的位置不一定相同，于是可以采取根据两数组的不同对齐方式取找最长子数组 下述代码中分两步进行：

首先是A不变，B的首元素依次和A中的某个元素对齐，求解最长的重复子数组，求解的过程中如果两个字符相等，递增变量；否则，将变量置为0，在这个过程中要不断更新结果数组然后是B不变，A的首元素依次和B中的某个元素对齐。接下来的过程是一样的

时间复杂度：O（（N +Ｍ）* min（N，M））

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { //滑动窗口 int res = 0, cur, k; for(int i = 0; i < A.size(); ++i){//以A为基准，滑动B cur = 0; k = i; for(int j = 0; j < B.size() && k < A.size(); ++j,++k){ if(A[k] == B[j]) ++cur; else cur = 0; res = max(res, cur); } } for(int i = 0; i < B.size(); ++i){//以B为基准，滑动A cur = 0; k = i; for(int j = 0; j < A.size() && k < B.size(); ++j, ++k){ if(B[k] == A[j]) ++cur; else cur = 0; res = max(res, cur); } } return res; } };

基本思想3：暴力

求数组A中从 i 开始和数组B中从 j 开始的最长重复子数组，时间复杂度为O（n³）