题目描述

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

样例

算法1：暴力枚举

(暴力枚举)

枚举A中每个以A[i]结尾的子数组x { O(n^2),即以A[i]结尾的数组长度最长从1到i-1 }
枚举B中每个以B[j]结尾的子数组y { O(n^2),即以B[i]结尾的数组长度最长从1到j-1 }
然后判断x和y是否相等

时间复杂度 O(n^4)

暴力枚举的特点： 有限集，但是时间复杂度太高，那么可以使用DP,动态规划。

算法2：DP

算法思路：

状态表示： f[i][j] 集合：表示A中以A[i] 和 B中以B[j]结尾的公共子数组的集合，
属性：最长长度
状态计算： (以A[i]和B[j]是否相同划分)
若A[i] == B[j],则f[i][j] = f[i-1][j-1] + 1，即等于以A[i-1]和B[j-1]结尾的公共子数组的长度加1；
若A[i] != B[j],则表示不存在以A[i]和B[j]结尾的公共子数组；

时间复杂度 状态数量 x 状态计算 = n^2 * 1 = O(n^2)

C++ 代码

class Solution {
public:

    //DP，时间O（n^2）
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        vector<vector<int>> f(n+1, vector<int>(m+1,0));
        int res = 0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(A[i-1] == B[j-1]) f[i][j] = f[i-1][j-1]+1;
                else f[i][j] = 0;
                res = max(res, f[i][j]);
            }
        }
        return res;
    }
};