首页 > 试题广场 >

最长公共子数组

[编程题]最长公共子数组
  • 热度指数：1957 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个整数数组，求两个数组的最长的公共子数组的长度。子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
数据范围：两个数组的长度都满足 ，数组中的值都满足
示例1

输入

[1,2],[1,2]

输出

2

说明

最长的公共子数组是[1,2]
示例2

输入

[1,2,5,5,7,8],[2,5,7,8,5]

输出

3

说明

最长的公共子数组是[5,7,8]
示例3

输入

[1,2],[1,3,2]

输出

1

说明

最长的公共子数组是[1]
算法知识视频讲解
添加回答
Java
pein531头像 pein531
本质是最长公共子串问题，设dp[i][j]表示以A[i]结尾和以B[j]结尾的最长公共子数组。
  1. 如果A[i]=B[j]，说明可以在“以A[i - 1]结尾和以B[j-1]结尾”的最长公共子数组的基础上增加一个长度，因此状态转移方程为：dp[i][j] = dp[i - 1][j - 1] + 1；
  2. 如果A[i]≠B[j]，说明在此处公共子数组断了，不存在以A[i]结尾和以B[j]结尾的公共子数组，dp[i][j]=0。
由于某个普遍位置的取值仅依赖于它左上角的值，因此填表的顺序为从上到下，从左往右。时间复杂度和空间复杂度均为O(nm)。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param B int整型一维数组 
     * @return int整型
     */
    public int longestCommonSubarry (int[] A, int[] B) {
        // write code here
        int[][] dp = new int[A.length + 1][B.length + 1];
        int maxLen = 0;
        for(int i = 1; i <= A.length; i++){
            for(int j = 1; j <= B.length; j++){
                if(A[i - 1] == B[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
        return maxLen;
    }
}
发表于 2021-12-13 10:38:47 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A int整型一维数组 
 * @param B int整型一维数组 
 * @return int整型
*/
func longestCommonSubarry( A []int ,  B []int ) int {
    m,n:=len(A),len(B)
    mat:=make([][]int,m+1)
    for i,_:=range mat{
        mat[i]=make([]int,n+1)
    }
    ans:=0
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if A[i]==B[j]{
                mat[i+1][j+1]=mat[i][j]+1
                if mat[i+1][j+1]>ans{
                    ans=mat[i+1][j+1]
                }
            }
        }
    }
    return ans
}

发表于 2023-03-08 08:47:51 回复(0)
Java
blue&&lan头像 blue&&lan 
public int longestCommonSubarry (int[] A, int[] B) {
        int m=Integer.MIN_VALUE;
        for(int i=0;i<A.length;i++){
            int k=i,j=0,c=0;
            while(j<B.length){
                if(k<A.length&&A[k]==B[j]){
                    k++;
                    j++;
                    c++;
                    m=Math.max(m,c);
                }else{
                    k=i;
                    c=0;
                    if(A[k]!=B[j])
                    j++;
                }
            }
        }
        return m;
    }

发表于 2022-06-02 16:55:14 回复(0)
提交观点

问题信息

动态规划
难度：
3条回答 1189浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号