这题上来直觉告诉我是利用动态规划的思想 遇到这两个数组的，通常是用二维DP数组 我们可以简单画个表看看
3 2 1 4 7 1 0 0 1 0 0 2 0 1 0 0 0 3 1 0 0 0 0 2 0 2 0 0 0 1 0 0 3 0 0这里我们按照表格形式初始化dp数组 只不过多加了一行一列 因此下面dp数组会相对于A B两个数组多一个1，需要减去
我们假设dp[i][j] 代表以A[i-1] B[j-1]结尾的公共子串长度 当A[i-1] == B[j-1] 则更新dp[i][j] = dp[i-1][j-1] + 1 代码如下
from typing import * class Solution: def findLength(self, A: List[int], B: List[int]) -> int: """ 动态规划 3 2 1 4 7 1 0 0 1 0 0 2 0 1 0 0 0 3 1 0 0 0 0 2 0 2 0 0 0 1 0 0 3 0 0 :param A: :param B: :return: """ l1 = len(A) l2 = len(B) dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)] maxval = 0 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 maxval = max(dp[i][j], maxval) return maxval由于是DP申请MXN大小数组，且遍历一遍 所以时间复杂度和空间复杂度均为O(MxN)
第二种方法则是滑动窗口法 重复子数组的起始地方，在A,B中是不同的 但我们将A或B数组适当偏移 ，则起始位置是相同的 所以我们就有了这个方法 先对A或B数组进行偏移，再在里面遍历一遍 而A，B数组偏移又有两种方法
A不动B偏移B不动A偏移 我们基于这两类，分别做一个for循环 def findLengthv2(self, A, B): def maxLength(addA, addB, length): """ 通过addA， addB来表示窗口偏移量 :param addA: :param addB: :param length: :return: """ ret = 0 k = 0 for i in range(length): if A[addA+i] == B[addB+i]: k += 1 ret = max(ret, k) else: k = 0 return ret l1, l2 = len(A), len(B) ret = 0 for i in range(l1): length = min(l2, l1-i) # 第一种情况，A窗口动 B不动 ret = max(ret, maxLength(i, 0, length)) for i in range(l2): length = min(l1, l2-i) # 第一种情况，A窗口不动 B窗口动 ret = max(ret, maxLength(0, i, length)) return ret S = Solution() # a = S.findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]) a = S.findLengthv2([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]) print(a)