718. 最长重复子数组

题目描述

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

示例：

输入: 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

解题思路

遇到熟悉题目的第四天，开心。本来是想截图题目描述的，但是发现会加水印，但是这道题又不是我原创的，而且因为这个鬼机制，主页地址是qq加一堆数字，好丑。所以没办法，还是老老实实复制题目描述并排格式。这道应该也是面试必会的一道了，自己秋招时虽然没被问到，但是小伙伴被问到的次数还蛮多的。而且这道题有很多版本，进阶一点点的要把公共子数组输出，还有最长公共子串（子串不像子数组是连续的）什么的，今天这篇都会简单说说，把代码贴上，但不会细说，等到时候碰上再说，懒。。。而且写给自己看，也没必要。

首先这题比较大众的思路肯定是用动态规划，其实我第一次做也想不到动态规划，算是训练后的大众思路吧。创建个二维数组来记录最长公共子数组的长度，注意二维数组的size是要比两个数组的长度大一号的，即(m+1)*(n+1)大小，因为第一行和第一列要用来记录初状态。具体思路是判断两个数组的当前位置元素是否有相同，如果相同则在dp内上一状态的基础上+1，即状态转移方程是dp[i][j] = dp[i-1][j-1] + 1，其中dp[i][j]是当前状态，dp[i-1][j-1] 是上一状态；如果不相同则dp的相应位置置0。初条件全为0，因为在一开始未对比的时候，是没有相同元素的。截止条件当然就是两个数组内的所有元素都被遍历过了即截止。不过用动态规划似乎时间和空间复杂度都不怎么样，都是O(N×M)。

细节的部分在代码部分都加了注释，应该很详细。

题解代码：

def findLength(self, A: List[int], B: List[int]) -> int: if not A or not B: return 0 m = len(B) + 1 # 创建dp的size，+1是为了留有初条件的空间 n = len(A) + 1 # 创建时尽量不要用[[0]*n]*m 这样子，因为这样子创建出来的二维数组似乎不是独立的，某一个元素变化，好像整行或者列都会变 dp = [[0 for i in range(n)] for i in range(m)] # 初条件为0，所以不如就全部置0处理 key = 0 # 记录最长的公共子数组 # 这里似乎有思路是倒着走的，我也不知道为啥要倒着走，反正我觉得不如这种正着走顺当 for i in range(1,m): for j in range(1,n): if A[j-1] == B[i-1]: # 判断对应位置上元素是否相同 dp[i][j] = dp[i-1][j-1] + 1 # 状态转移 key = max(key, dp[i][j]) # 取最长 # 这里没有状态转移方程的另外一半，因为我们之前就已经对整个dp都置0了。没必要额外再有改0的操作 return key

那如果进阶一点，要输出这个公共子数组（或者子串），就是额外再增加一个p，来标定最长公共子串结束的位置。是技术处时候，由这个位置向前推key的长度然后输出就好。代码是针对的是最长公共子串，即是两个字符串而不是两个数组，其实最长公共子数组也基本一模一样。

# 最长公共子串 def substr(s1,s2): maxl = 0 A = [[0 for i in range(len(s1)+1)] for i in range(len(s2)+1)] for i in range(1,len(s2)+1): for j in range(1,len(s1)+1): if s1[j-1] == s2[i-1]: A[i][j] = A[i-1][j-1]+1 if maxl < A[i][j]: maxl = A[i][j] p = i # 就是这里，记录末位置 return maxl, s2[p-maxl:p]

还有更进阶，最长公共子序列（不连续）。思路差不多，都是动态规划，不过在输出子序列的时候麻烦一点，因为要一步步回溯哪些元素是公共的。

# 最长公共子序列 def subseq(s1,s2): # dp矩阵 A=[[0 for i in range(len(s1)+1)] for i in range(len(s2)+1)] # 记录路径的矩阵 B = [[' ' for i in range(len(s1)+1)] for i in range(len(s2)+1)] for i in range(1,len(s2)+1): for j in range(1,len(s1)+1): if s2[i-1] == s1[j-1]: A[i][j] = A[i-1][j-1]+1 B[i][j] = '+1' else: A[i][j] = max(A[i-1][j],A[i][j-1]) if A[i][j-1] == A[i][j]: B[i][j] = 'left' else: B[i][j] = 'up' return B,A[-1][-1] def findseq(B,s1,s2): # 回溯的函数，需要上个函数记录路径的矩阵 j = len(s1) i = len(s2) res = [] while i >0 and j>0: if B[i][j] == 'left': j -= 1 elif B[i][j] == 'up': i -= 1 else: i -= 1 j -= 1 res.append(s1[j]) return ''.join(res[::-1]) s1='helloworld' s2='loop' B, n = subseq(s1, s2) print(n) print(findseq(B,s1,s2))

官方思路

在看了官方题解之后了解到这道题也能用滑窗做，神奇。时间复杂度给出的是O((N+M)×min(N,M))，然而我并不知道是怎么算出来这个时间复杂度的。小白嘛，没办法。空间复杂度是O(1)

具体思路就是取较短数组的子数组和较长的数组去比，看这个子数组是否在较长的数组内部。在滑窗内的是这个子数组，如果子数组在长数组的内部，就继续向滑窗内加元素（右边界向右拓展）；如果不在，则左边界向左收缩。需要注意的是对于数组来说，只能判断某个元素是否在数组内，而没法判断某个数组是不是其连续子数组（也可能是有现成函数的，只是我不知道）。所以这里我的做法是将数组都转成字符串，这样就可以通过判断是否为子串来判断是否为连续子数组了。细节注释在了代码里，应该还算详细。

def findLength(self, A: List[int], B: List[int]) -> int: if not A or not B: return 0 m = len(A) n = len(B) # 保证取短的数组 if m > n: m, n, B, A = n, m, A, B # 将数组转化为字符串 ''' 前后加逗号的原因是保证为单一的元素，比如子串是‘7’，那么在长数组中 只要含‘7’都会被判找到，这样像‘27’、‘79’、‘371’这种其实并不是‘7’的 数字都会误判。 ''' strB = ',' + ','.join(str(x) for x in B) + ',' tmp = [] # 滑窗 key = 0 for x in A: tmp.append(x) # 相当于右边界拓展 str_tmp = ',' + ','.join(str(y) for y in tmp) + ',' if str_tmp in strB: key = max(len(tmp), key) else: tmp = tmp[1:] # 左边界收缩 return key

以上就是我，一个正儿八经的小白（大神们通过看代码应该也感觉出来了），对这道题的理解，欢迎诸位指正讨论，感谢阅读。

原题链接：

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/