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

方法一：暴力

本题很容易想到一个暴力解法，暴力解法的时间复杂度是$O(N^3)$，代码如下。值得注意的是如果不对暴力解法进行优化，实会超时的。所以在第一层循环中加入if(m-i<max_length) break;即剩下需要遍历的字符串长度小于当前长度最大的公共子序列就可以直接退出了。虽然可以通过测试，但是速度非常慢。

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

方法二：动态规划

思路：首先，上述暴力算法速度慢的根本原因在于，同一个数字将会多次比较，那么最好的情况是每个数字只比较一次。如果说将$A$中的元素（假设A中有M个元素）与$B$中的元素（B中有N个元素）都进行比较并且只比较他们是否相等，那么写两层for循环即可，时间复杂度为$O(MN)$，但是按照题目要求来看只是比较是不行的，至少需要将比较的结果存放起来，所以需要创建一个数组$a[i][j]$，将$A[i]$与$B[i]$的比较结果进行保存。假设相同置1不同置0，最后我们得到一个矩阵$a$，接着我们应该根据这个矩阵去判断最长的公共子序列。所以满足什么样的条件才是公共子序列呢？由于公共子序列必须是连续的，那么假设$A[i-1]=B[j-1]$，如果$A[i]=B[j]$则这一公共子序列的长度应该增加1。那么我们是不是可以用一个$dp[i][j]$。 如果$A[i]==B[j]$则 $$dp[i][j]=d[i-1][j-1]+1$$ 否则 $$dp[i][j]=0$$ 所以dp中的最大值就是最长公共子序列的长度。算法复杂度$O(MN)$,代码如下：

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

方法三：滑动窗

把两个数组上下摆放，那么他们对齐的方式一共有M+N种，如下几种方式。可以看到每种对齐方式，会产生不同大小的重叠部分，称之为窗，如果遍历所有的对齐方式，并且判断每种窗里面的最长重复字串，那么可以获得两个数组的最长重复字串。算法时间复杂度$O((M+N)\ast min(M,N))$，空间复杂度$O(1)$。另外划窗有一个很有意义的强化，就是优先从最大公共区间开始减小窗口。当窗口len<ret时，已经可以直接break了。

123412345 123412345 123412345

代码：

class Solution { public: int window_find(vector<int>& A, vector<int>& B, int lenth, int ind_A, int ind_B) { int ret = 0, k=0; for(int i=0; i<lenth; ++i) { if(A[ind_A+i]==B[ind_B+i]) { k++; }else{ k = 0; } ret = max(ret, k); } return ret; } int findLength(vector<int>& A, vector<int>& B) { int m = A.size(), n = B.size(); int min_len = min(m, n); int ret = 0; for(int i=0; i<m; ++i) { int lenth = min(i+1, min_len); ret = max(window_find(A, B, lenth, m-i-1, 0), ret); } for(int i=1; i<n; ++i) { int lenth = min(min_len, n-i); ret = max(window_find(A, B, lenth, 0, i), ret); } return ret; } };