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

题意整理

• 给定两个整数数组，求两个数组的最长的公共子数组的长度。

方法一（动态规划）

1.解题思路

• 状态定义：dp[i][j]表示A的子数组以i-1结尾，B的子数组以j-1结尾时的最长公共子数组长度。
• 状态转移：两层循环，遍历A数组和B数组中每一个元素，如果当前元素相等，则由左上方对应位置状态加1，即$dp[i][j]=dp[i-1][j-1]+1dp[i][j]=dp[i-1][j-1]+1$，否则重置为0。每次取所有可能的最大值。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param B int整型一维数组 
     * @return int整型
     */
    public int longestCommonSubarry (int[] A, int[] B) {
        int m=A.length;
        int n=B.length;
        //dp[i][j]表示A的子数组以i-1结尾，B的子数组以j-1结尾时的最长公共子数组长度
        int[][] dp=new int[m+1][n+1];
        int res=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //如果相等，则由左上方对应位置加1
                if(A[i-1]==B[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                //否则重新置为0
                else{
                    dp[i][j]=0;
                }
                //取所有可能的最大值
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：总共两层循环，所以最终的时间复杂度是$O(m\ast n)O(m*n)$。
• 空间复杂度：需要额外大小为$(m+1)\ast (n+1)(m+1)*(n+1)$的dp空间，所以空间复杂度为$O(m\ast n)O(m*n)$。

方法二（空间优化）

1.解题思路

与方法一思路差不多。不过由于每次状态转移，只与上一行左边元素，即左上角元素相关。所以只需一维空间就足够了，另外用一个变量记录上次被覆盖的左上角元素，状态转移之后，将这个记录赋值给upLeft，那么下次进行状态转移的时候就不会因为覆盖而出错。

图解展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param B int整型一维数组 
     * @return int整型
     */
    public int longestCommonSubarry (int[] A, int[] B) {
        int m=A.length;
        int n=B.length;
        //dp[j]表示每一行B的子数组以j-1处结尾的最长子数组长度
        int[] dp=new int[n+1];
        int res=0;
        for(int i=1;i<=m;i++){
            //记录左上角位置
            int upLeft=dp[0];
            for(int j=1;j<=n;j++){
                //记录即将被覆盖的左上角的值
                int temp=dp[j];
                //如果相等，则由左上角对应值加1
                if(A[i-1]==B[j-1]){
                    dp[j]=upLeft+1;
                }
                //否则重置为0
                else{
                    dp[j]=0;
                }
                //跟新左上角的值
                upLeft=temp;
                res=Math.max(res,dp[j]);
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：总共两层循环，所以最终的时间复杂度是$O(m\ast n)O(m*n)$。
• 空间复杂度：需要额外大小为n+1的dp数组，所以空间复杂度为$O(n)O(n)$。