一、题目描述

给两个整数数组 AB ,返回两个数组中公共的、长度最长的子数组的长度。

示例:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出:3
解释:
长度最长的公共子数组是 [3, 2, 1] 。

提示:

  • 1 <= len(A), len(B) <= 1000
  • 0 <= A[i], B[i] < 100

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长重复子数组( LeetCode 718 ):https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
class Solution {
    public int findLength(int[] nums1, int[] nums2) {

        // 获取 nums1 的长度
        int m = nums1.length;

        // 获取 nums2 的长度
        int n =  nums2.length;

        // 设置数组 dp,用来存储 nums1 和 nums2 公共的、长度最长的子数组的长度
        // dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        // dp[2][3] 表示 nums1 前 2 个元素和 nums2 前 3 个元素的公共的、长度最长的子数组的长度
        // dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
        // 前 i 个元素的区间为 [ 0 , i - 1 ]
        // dp[m][n] 表示 nums1 前 m 个元素和 nums2 前 n 个元素的公共的、长度最长的子数组的长度
        // 前 m 个元素的表示区间为 [ 0 ,m ],前 n 个元素的表示区间为 [ 0 ,n ]
        // 因此,dp 数组的长度为 m + 1 和 n + 1
        int[][] dp = new int[m + 1][n + 1];

        // maxLength 表示 dp 数组中的最大值
        int maxLength = 0;

        // dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
        // nums1 nums2 也没有元素
        // 因此,公共的、长度最长的子数组的长度为 0
        dp[0][0] = 0;

        // nums1 没有元素 或者 nums2 没有字符时,公共的、长度最长的子数组的长度都为 0
        for( int i = 0 ; i <= m ; i++){
            dp[i][0] = 0;
        }

        for( int j = 0 ; j <= n ; j++){
            dp[0][j] = 0;
        }

        // i 从 1 开始,直到 m 位置,遍历 nums1 的前 i 个元素
        for (int i = 1; i <= m; i++) {

            // j 从 1 开始,直到 n 位置,遍历 nums2 的前 j 个元素
            for (int j = 1; j <= n; j++) {

                // 如果发现 nums1 的当前元素,即位置为 i - 1 的元素
                // 与 nums2 的当前元素,即位置为 j - 1 的元素【相同】
                // 此时,找到了一个公共元素,公共的、长度最长的子数组的长度加 1
                if (nums1[i - 1] == nums2[j - 1]) {

                    // dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
                    // dp[i - 1][j - 1] 表示 nums1 前 i - 1 个元素和 nums2 前 j - 1 个元素的公共的、长度最长的子数组的长度
                    dp[i][j] = dp[i - 1][j - 1] + 1;

                    // 更新最长的子数组长度
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }

        // 返回结果
        return maxLength;
    }
}

2、C++ 代码

3、Python 代码

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注