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在开始解决问题之前，先分析问题。题目要求计算两个数组的最长公共子数组。从示例中可以看出，子数组在原始数组中应该是连续的。那么，我们就可以使用暴力解法来尝试一一比较。示例代码大致如下：classSolution:deffindLength(self,A:List[int],B:List[int])->int:ans=0foriinrange(len(A)):forjinrange(len(B)):length=0whilei+lengthint:A_length=len(A)B_length=len(B)max_length=0dp=[[0]*(B_length+1)for_inrange(A_length+1)]#dp[i][j]由dp[i+1][j+1]转，所以从右向左遍历求解foriinrange(A_length-1,-1,-1):forjinrange(B_length-1,-1,-1):如果A[i]==B[j]:dp[i][j]=dp[i+1][j+1]+1否则:dp[i][j]=0max_length=max(max_length,dp[i][j])returnmax_length#滑动窗口类解决方案：deffindLength(self,A:List[int],B:List[int])->int:defget_max_length(a_start,b_start,length):max_length=0count=0#计算这个区域，i的最长公共子串的长度inrange(length):ifA[a_start+i]==B[b_start+i]:count+=1max_length=max(max_length,count)else:count=0returnmax_lengthA_length=len(A)B_length=len(B)ans=0#固定A，移动B，使B的第一个元素对应于A的一个元素foriinrange(A_length):length=min(A_length-i,B_length)ans=max(ans,get_max_length(i,0,length))#固定B，移动A，使A的第一个元素对应于Bforjinrange(B_length):length=min(A_length,B_length-j)ans=max(ans,get_max_length(0,j,length))returnans实现结果实现结果|动态规划实现结果|滑动窗口总结题目要求，两个数组的最长公共子数组，那么可以考虑使用暴力破解的方式来尝试解题。逐个枚举数组A和数组B的每个元素是否相同，计算最长公共前缀的长度，循环直到结束。维护和更新长度，取最大值。（执行结果超时）虽然暴力破解的执行会超时，但是可以看出它还是有不足之处。因为在最坏的情况下，对于任意i，j，A[i]和B[j]的比较次数为min(i+1,j+1)。可以考虑从这个方向优化算法，这里可以考虑使用动态规划。当我们确定A[i]==B[j]时，此时的公共前缀长度为1，A[i:]和B[j:]的公共前缀长度将等于A[i+1:]和B[j+1:]的公共前缀长度加上当前公共前缀长度1，否则A[i:]和B[j:]的公共前缀长度为0。设dp[i]这里的[j]表示A[i:]和B[j:]的公共前缀长度，dp[i][j]的结果分为两种情况：当A[i]==B[j],然后dp[i][j]=dp[i+1][j+1]+1;否则，dp[i][j]=0这道题也可以用滑动窗口的方法求解。在前面的算法中我们可以看到，都需要一个一个比较，才能算出长度。这是因为两个数组的重复部分从不同的位置开始。也就是说，当起始位置确定后，从当前位置开始遍历也可以得到结果。主要难点在于，如果两个数组对齐，可以分为以下几种情况：先固定A，移动B，使B的第一个元素与数组A的一个元素对齐；或者固定B并移动A，使A的第一个元素与数组AB中的一个元素对齐。文章原创，欢迎关注和点赞。微信公众号《书所集录》同步更新，也欢迎大家关注。
