Leetcode718. 最长重复子数组

题目描述

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

解题思路

这道题和最长公共子序列有些类似，又有些不同。我们可以考虑使用动态规划法和滑动窗口法求解。

方法一：动态规划法

我们可以借鉴使用动态规划法求解最长公共子序列的思路，用$dp[i][j]$来表示$A[0 \cdots i]$和$B[0 \cdots j]$的最长公共子数组。那么，我们就可以很容易地得到状态转移方程：

$$if \quad A[i]==B[j] \quad then \quad dp[i+1][j+1]=dp[i][j]+1 \\ if A[i] \neq B[j] \quad then \quad dp[i+1][j+1]=0$$

根据状态转移方程，我们很容易写出对应的代码。但是，需要注意数组越界的问题。

时间复杂度为 ：$O(MN)$

空间复杂度为：$O(MN)$ 但是可以通过滚动数组把空间复杂度优化到$O(1)$

方法二：滑动窗口法

滑动窗口法通常用来解决一些在连续区间上的问题。通常需要确定一个窗口，然后通过动态地滑动去解决问题。

这道题我们先让A数组不动，让B数组去滑动，那么此时的窗口就是A数组和B数组从开始处对齐后的公共部分，如下图红框所示。然后在红框内去遍历求解窗口内的最长公共子数组。遍历完成后，我们再让A数组滑动，B数组不动，类似地重复以上过程。最后的答案就是所有窗口内最长公共子数组的最大值。

下图展示了模拟图，用来加强理解。和代码并不完全一致。

时间复杂度为：$O((N+M) \times min(N,M))$

空间复杂度为：$O(1)$

示例代码

方法一：动态规划法

int findLength(vector<int>&nums1,vector<int>&nums2)
{
    int ans=0;
    vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
    for(int i=0;i<nums1.size();++i)
    {
        for(int j=0;j<nums2.size();++j)
        {
            if(nums1[i]==nums2[j])
            {
                dp[i+1][j+1]=dp[i][j]+1;
            }
            else{
                dp[i+1][j+1]=0;
            }
            ans=max(ans,dp[i+1][j+1]);
        }
    }
    return ans;
}

方法二：滑动窗口法

int maxLength(vector<int>&nums1,vector<int>&nums2,int add1,int add2,int length)
{
    int count=0,ret=0;
    for(int i=0;i<length;++i)
    {
        if(nums1[add1+i]==nums2[add2+i])
        {
            count++;
        }
        else{
            count=0;
        }
        ret=max(ret,count);
    }
    return ret;
}

int findLength(vector<int>&nums1,vector<int>&nums2)
{
    int ret=0;
    for(int i=0;i<nums1.size();++i)
    {
        int len=min(nums2.size(),nums1.size()-i);
        int maxlen=maxLength(nums1,nums2,i,0,len);
        ret=max(ret,maxlen);
    }
    for(int i=0;i<nums2.size();++i)
    {
        int len=min(nums1.size(),nums2.size()-i);
        int maxlen=maxLength(nums1,nums2,0,i,len);
        ret=max(ret,maxlen);
    }
    return ret;

}