题解 | #最长公共子数组#

最长公共子数组

题目描述

给定两个整数数组，求两个数组的最长的公共子数组的长度。子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。

方法一：动态规划的方法

解题思路

对于本题，采用动态规划的方法进行求解，dp[i][j]表示一个数组中下标i结尾和另一个数组下标j结尾的公共子数组的长度。并且有状态转移方程：

1、如果两数组下标位置的数值相同

$dp[i][j]=dp[i-1][j-1]+1dp[i][j]\; =\; dp[i-1][j-1]\; +1$

2、如果不相同

$dp[i][j]=0dp[i][j]\; =\; 0$

解题代码

class Solution {
public:
    int dp[1001][1001]={0}; // 根据题目数据的范围来创建dp数组
    int longestCommonSubarry(vector<int>& A, vector<int>& B) {
        int n=A.size(),m=B.size();
        int res=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(A[i-1]==B[j-1])
                {//如果相等，则+1
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {//否则，置为0
                    dp[i][j]=0; 
                }
                res=max(res,dp[i][j]);//维护最大值
            }
        }
        return res; // 返回结果
    }
};

复杂度分析

时间复杂度：二层循环，因此时间复杂度为$O(n^2)O(n^2)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：java的方法

解题思路

思路同方法一。

解题代码

import java.util.*;

public class Solution {
    int[][] dp=new int[1001][1001];
    public int longestCommonSubarry (int[] A, int[] B)
    {
        int n=A.length,m=B.length;
        int res=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(A[i-1]==B[j-1])
                {//如果相等，则+1
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {//否则，置为0
                    dp[i][j]=0; 
                }
                res=Math.max(res,dp[i][j]);//维护最大值
            }
        }
        return res; // 返回结果
    }
}

复杂度分析

时间复杂度：二层循环，因此时间复杂度为$O(n^2)O(n^2)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$