[C++] LeetCode 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

题解

这题最直观的解法是用DP，代码如下：

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n=A.size(),m=B.size(),res=0;
        vector<vector<int>> vec(n,vector<int>(m,0));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0||j==0) vec[i][j]=A[i]==B[j];
                else if(A[i]==B[j]) vec[i][j]=vec[i-1][j-1]+1;
                else vec[i][j]=0;
                res=max(res,vec[i][j]);
            }
        }
        return res;
    }
};           

但是开二维数组比较浪费空间，所以可以考虑用滚动数组，开一个一维数组即可。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int n=A.size(),m=B.size(),res=0;
        vector<int> vec(m,0);
        for(int i=0;i<n;i++){
            for(int j=m-1;j>=0;j--){
                if(A[i]==B[j]) vec[j]=1+(j>0?vec[j-1]:0);
                else vec[j]=0;
                res=max(res,vec[j]);
            }
        }
        return res;
    }
};