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

## 题目描述

[718. 最长重复子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)

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

## 解题思路

[最长重复子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/)

### 动态规划

本题可以看做是**最长公共子串**由字符串推演到数组, 因此可以用相同的解法. 使用动态规划时, 二维状态矩阵中, $$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. 代码为:

```python
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]$$有关, 因此在迭代时, 我们可以按照对角线进行迭代, 这样二维状态矩阵可以简化为**标量**.

```python
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)$$.

### 滑动窗口

![](/files/-MI7Nrd6zEXhTy7Poeye)

参考: [【手绘图解】两种解法：DP 和 滑动窗口](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zhe-yao-jie-shi-ken-ding-jiu-dong-liao-by-hyj8/)

* 首先, A固定, 移动B, 逐个求出公共子数组中的长度, 其中A指的上面的\[1,2,3,2,1]数组, B指的是下面的数组
* 然后, B固定, 移动A, 逐个求出公共子数组中的长度
* 综合比较出最长的长度

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

```python
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\]\[中等\]\[动态规划\] 最长公共子序列](/garnet/suan-fa/dong-tai-gui-hua/1143-zui-chang-gong-gong-zi-xu-lie.md)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/hua-dong-chuang-kou/718-zui-chang-zhong-fu-zi-shu-zu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.