官方链接

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

方案：

1. 滑动窗口

右指针遍历短的列表（A）:
(1) 如果此时的局部列表（tmp_list）在另一个列表（B）中，计算局部列表（tmp_list）的长度；
(2) 否则，向右移动左指针（此处是伪左指针）；

class Solution:def findLength(self, A: List[int], B: List[int]) -> int:m = len(A)n = len(B)if m>n:m, n, A, B = n, m, B, Atmp_list = []result = 0str_B = ',' + ','.join([str(i) for i in B]) + ','for r in A:tmp_list.append(str(r))if ',' + ','.join(tmp_list) + ',' in str_B:result = max(result, len(tmp_list))else:tmp_list = tmp_list[1:]return result

2. 滑动窗口（参考：错开比较法）

这个方案比较耗时，暂时未想到进一步的优化方案。

具体代码如下：

class Solution:def findLength(self, A: List[int], B: List[int]) -> int:m = len(A)n = len(B)if m>n:m, n, A, B = n, m, B, Aresult = 0def max_length(a, b):"""len(a) == len(b)"""cur_result = 0count = 0for i in range(len(a)):if a[i] == b[i]:count += 1else:cur_result = max(cur_result, count)count = 0cur_result = max(cur_result, count)return cur_resultfor i in range(1, m+1):tmp_list_A = A[-i:]tmp_list_B = B[:i]if len(tmp_list_A) <= result:continueresult = max(result, max_length(tmp_list_A, tmp_list_B))for i in range(n-m):tmp_list_A = A tmp_list_B = B[i+1: len(tmp_list_A)+i+1]if len(tmp_list_A) <= result:continueresult = max(result, max_length(tmp_list_A, tmp_list_B))for i in range(1, m+1):tmp_list_A = A[: m-i]tmp_list_B = B[-m+i: ]if len(tmp_list_A) <= result:continueresult = max(result, max_length(tmp_list_A, tmp_list_B))return result

3. 动态规划

 

 

class Solution:def findLength(self, A: List[int], B: List[int]) -> int:if not A or not B:return 0m = len(A)n = len(B)max_value = 0dp = [[0] * (m+1) for _ in range(n+1)]for i in range(1, m+1):for j in range(1, n+1):if A[i-1] == B[j-1]:dp[i][j] = dp[i-1][j-1] + 1max_value = max(max_value, dp[i][j])return max_value