(24)718. 最长重复子数组

题目链接： https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/ 困难度：中等 718. 最长重复子数组 给两个整数数组 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: ]的最长公共前缀 dp[i-1][j-1] = dp[i][j]+! 或者 0 （ A[i] == B[j] ） 不过执行时间和内存消耗都挺高的

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; } };

还有个思路是滑动窗口 之前做题用过 这个没想到 好垃圾 以A B分别为基准 如 使A不动 B滑动 B[i]为开始（i范围为 0-(n-1)） 得到 A 与B[i:] 之间的公共前缀

class Solution { public: // a--A b--B a,b有一个为0 若a为0 则此时A不动 int maxLength(vector<int>& A, vector<int>& B, int a, int b, int len) { int ret = 0, k = 0; for (int i = 0; i < len; i++) { if (A[a + i] == B[b + i]) { k++; } else { k = 0; } ret = max(ret, k); } return ret; } int findLength(vector<int>& A, vector<int>& B) { int n = A.size(), m = B.size(); int ret = 0; // for (int i = 0; i < n; i++) { int len = min(m, n - i); int maxlen = maxLength(A, B, i, 0, len); ret = max(ret, maxlen); } for (int i = 0; i < m; i++) { int len = min(n, m - i); int maxlen = maxLength(A, B, 0, i, len); ret = max(ret, maxlen); } return ret; } };

官网还有一种方法 没看懂 有时间在说。。。