题意整理

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

方法一(动态规划)

1.解题思路

  • 状态定义:dp[i][j]表示A的子数组以i-1结尾,B的子数组以j-1结尾时的最长公共子数组长度。
  • 状态转移:两层循环,遍历A数组和B数组中每一个元素,如果当前元素相等,则由左上方对应位置状态加1,即dp[i][j]=dp[i1][j1]+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(mn)O(m*n)
  • 空间复杂度:需要额外大小为(m+1)(n+1)(m+1)*(n+1)的dp空间,所以空间复杂度为O(mn)O(m*n)

方法二(空间优化)

1.解题思路

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

图解展示: alt

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(mn)O(m*n)
  • 空间复杂度:需要额外大小为n+1的dp数组,所以空间复杂度为O(n)O(n)