[718][中等][动态规划][滑动窗口] 最长重复子数组

题目描述

718. 最长重复子数组

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

解题思路

最长重复子数组

动态规划

本题可以看做是最长公共子串由字符串推演到数组, 因此可以用相同的解法. 使用动态规划时, 二维状态矩阵中, $C[i][j]$看做是以$A[i]$和$B[j]$两个数字为结尾的子数组的公共子串的长度, 自然有:

• $C[i][j]=C[i-i][j-1] + 1, \quad A[i]=B[j]$
• $C[i][j]=0, \quad A[i] \ne B[j]$

边界状态全部为0. 代码为:

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

时间和空间复杂度都为$O(NM)$.

滚动数组

为了节省动态规划中使用的二维状态矩阵的空间, 使用滚动数组的思路进行优化.

从上面的状态转移公式中可以看出, $C[i][j]$的值只与左上角的$C[i-i][j-1]$有关, 因此在迭代时, 我们可以按照对角线进行迭代, 这样二维状态矩阵可以简化为标量.

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        n, m = len(A), len(B)
        if n > m:
            A, B = B, A
            n, m = m, n
        cache = 0
        max_len = 0

        for i in range(-(n - 1), m):
            for j in range(n):
                if i < 0 or i >= m:
                    i += 1
                    continue

                if A[j] == B[i]:
                    if i == 0 or j == 0:
                        cache = 1
                    else:
                        cache += 1
                    max_len = max(max_len, cache)
                else:
                    cache = 0

                i += 1
        return max_len

时间复杂度仍为$O(NM)$, 空间复杂度降为$O(1)$.

滑动窗口

参考: 【手绘图解】两种解法：DP 和 滑动窗口

• 首先, A固定, 移动B, 逐个求出公共子数组中的长度, 其中A指的上面的[1,2,3,2,1]数组, B指的是下面的数组

• 然后, B固定, 移动A, 逐个求出公共子数组中的长度

• 综合比较出最长的长度

通过上图, 比较好理解滑动的整个过程, 即先固定一个, 滑动另一个, 然后从对齐位开始判断; 然后返回来固定滑动比较, 得到最终的结果. 实际代码实现为了方便, 可以从两个数组首位对齐开始, 分别依次滑动, 代码如下:

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        n, m = len(A), len(B)
        res = 0

        def count_length(length, a_start, b_start):
            r, k = 0, 0
            ta, tb = A[a_start:], B[b_start:]
            for i in range(length):
                if ta[i] == tb[i]:
                    k += 1
                    r = max(r, k)
                else:
                    k = 0
            return r

        for i in range(n):
            res = max(res, count_length(min(m, n - i), i, 0))
        for i in range(m):
            res = max(res, count_length(min(n, m - i), 0, i))
        return res

对应的时间复杂度为$O((N + M) \times \min(N,M))$, 空间复杂度为$O(1)$.

相关题目

• [1143][中等][动态规划] 最长公共子序列