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

目录

1、题目分析

2、解题分析

3、代码

示例 1:

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

1、题目分析

求两个数组公共的子数组的长度，那么可以用较短的那个字符串去匹配长的字符串，使用枚举法。像最长最短的往往都可以用动态规划，不过要找出动态转移方程来。

2、解题分析

主要说一下滑窗法，选取较短的那个作为滑动的数组。

• 声明一个临时数组，遍历较短的那个数组
• 将遍历到的元素添加到临时数组中去，然后判断得到的字符串有没有在较长的数组中
  • 如果在的话就更新公共子数组的长度
  • 如果不在的话那就从头开始，不要之前的元素
• 最后返回更新的最大长度

3、代码

class Solution:def findLength(self, A: List[int], B: List[int]) -> int:# 动态规划算法l1 = len(A) l2 = len(B) #dp[i][j]代表以A[i-1]与B[j-1]结尾的公共字串的长度,公共字串必须以A[i-1]，B[j-1]结束dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)] for i in range(1,l1+1): for j in range(1,l2+1): if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 return max(max(row) for row in dp)'''3 2 1 4 71 0 0 1 0 02 0 1 0 0 03 1 0 0 0 02 0 2 0 0 01 0 0 3 0 0'''#如果A或者B有一个数组是空的就直接返回Noneif not A or not B:return None#如果A的长度是大于B的长度,那就交换一下,因为我想让A当滑窗的那个数组if len(A)>len(B):A,B = B,A#对A和B做处理A = [str(i) for i in A]B = ','+','.join([str(i) for i in B])+','# B:',3,2,1,4,7,'# 为啥把B搞成这个鬼样子呢？因为避免出现歧义# 举个例子A=[7] B=[17]# temp = 7->',7,' 这样就不会出现歧义,否则就这样# temp = 7->7, 因为B是字符串呀,所以‘7,’ in B中,这样结果就出现误判了# 因此必须要把B和Temp搞成',xx,x,x,xx,'这个鬼样子#初始化结果和一个临时数组res = 0temp=[]for i in A:temp.append(i)if ','+','.join(temp)+',' in B:res = max(res,len(temp))else:temp = temp[1:]return res

总结：这个题目应该是考察的动态规划，但是在实际的操作中动态规划的时间复杂度和空间复杂度更高。