2020.07.01 周三 718最长重复子数组 题目：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例： 输入： 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 ——————————我是分割线—————————— 解法： 一.对于这个题而言这是个错误解法！！！因为时间超限！！！暴力检索法。 这是我看完题目后脑子里的第一种解题方法——暴力。 思想：A从第一个元素开始遍历，每个A元素遍历时寻找是否有B元素与A元素相同，若相同则length+1，最后返回最大长度。 代码：
# 一 暴力法 超时！！！ class Solution(object): def findLength(self, A, B): """ :type A: List[int] :type B: List[int] :rtype: int """ max_length = 0 for i in range(len(A)): for j in range(len(B)): length = 0 while i+length<len(A) and j+length<len(B) and A[i+length]==B[j+length]: length = length + 1 if length > max_length: max_length = length return max_length if __name__=='__main__': A = [1,2,3,2,1] B = [3,2,1,4,7] print(Solution.findLength(0,A,B))结果： 二.滑动窗口 思想：第一步：将数组A固定，移动B，使得B的首元素与A的某个元素对齐，找到重复数组的起始位置，计算长度。这是相对B而言把A前移。第二步：将数组B固定，移动A，使得A的首元素与B的某个元素对齐，找到重复数组的起始位置，计算长度。这是相对B而言把A后移。
示例： 提交界面： 代码：
class Solution(object): def findLength(self, A, B): """ :type A: List[int] :type B: List[int] :rtype: int """ def get_max_length(a,b,length): #a为A的初始位置 b为B的初始位置 max_length = 0 #初始化最大长度 count = 0 #相同元素的个数 for i in range(length): if A[a+i]==B[b+i]: #AB元素相同则count+1 max_length和选最大 count = count + 1 max_length = max(max_length,count) else: #AB元素不同则count=0 count = 0 return max_length #返回最大长度 A_len = len(A) B_len = len(B) max_len = 0 # 把A前移 for i in range(A_len): length = min(A_len-i,B_len) #每次遍历前把A-i 即代表长度-1 max_len = max(max_len,get_max_length(i,0,length)) #A从i开始 B从0开始 #把A后移 for j in range(B_len): length = min(A_len,B_len-j) max_len = max(max_len,get_max_length(0,j,length)) return max_len if __name__=='__main__': A = [1,2,3,2,1] B = [3,2,1,4,7] print(Solution.findLength(0,A,B))结果
