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

最长公共子数组

http://www.nowcoder.com/practice/6032826d387c4a10ad3690cce5fdb015

题意：

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

方法一：

动态规划

思路：

dp[i][j]表示数组A以A[i]结尾，数组B以B[j]结尾公共子数组的长度。

状态转移方程：
if(A[i-1]==B[j-1]){//如果相等，则+1
    dp[i][j]=dp[i-1][j-1]+1;
}else{//否则，置为0
    dp[i][j]=0;
}

class Solution {
public:
    int dp[1005][1005]={0};//dp[i][j]表示数组A以A[i]结尾，数组B以B[j]结尾公共子数组的长度
    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}),存储dp数组。$

方法二：

java实现

思路：

思路同方法一相同，根据状态转移方程实现。

import java.util.*;


public class Solution {
    int[][] dp=new int[1005][1005];//dp[i][j]表示数组A以A[i]结尾，数组B以B[j]结尾公共子数组的长度
    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;
    }
}