蓝桥杯入门即劝退（十七）最长重复子数组（dp问题）

╰+哭是因爲堅強的太久メ 2023-09-23 19:23 35阅读 0赞

**------持续更新蓝桥杯入门系列算法实例--------**

**如果你也喜欢Java和算法，欢迎订阅专栏共同学习交流！**

**你的点赞、关注、评论、是我创作的动力！**

**-------希望我的文章对你有所帮助--------**

> **前言：今天又回顾了一部分之前写过的算法题，加深记忆和印象，不断思考总结才能够掌握算法题中的各种技巧和细节，失之毫厘谬以千里。今天的这道题目也挺有意思的，刚开始以为自己能够做出来，但总差点思路，研究一番后才醒悟。与你共享我的思考成果！**

## 一、题目描述 ##

给两个整数数组 `nums1` 和 `nums2` ，返回 *两个数组中 **公共的** 、长度最长的子数组的长度* 。

**示例 1：**

>     输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
>     输出：3
>     解释：长度最长的公共子数组是 [3,2,1] 。

**示例 2：**

>     输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
>     输出：5

> **解题思路：** 1、这题有些许类似前面题目中**字符串最长公共前缀**，但是总体更难一些，以为所求的子数组与子序列不同，在于必须是有序的。
> 
> 2、例如数组 Array\[8,4,7,6,4\],其子数组必须是连续的，\{8,4,6\},\{4,6\}就不行，因为数组元素位置不可改变。
> 
> 3、采用dp（动态规划）来完成，新建一个dp二维数组，且其大小为（A+1）\*（B+1）A、B分别是两个数组的长度。
> 
> 4、设置两个循环，对于两个数组中的元素遍历其比对，如果有相同位置的元素相同即dp\[\]\[\]+1,最好手动去画一画，就能理解。（未赋值的元素默认是0）
> 
> 5、最后，使用Math.max()，如果找到更长的数组长度，更新数据，最后return即可。

## 二、代码实现 ##

public int findLength(int[] nums1, int[] nums2) {
            int Result=0;
            int dp[][]=new int [nums1.length+1][nums2.length+1];
            for(int i=1;i<nums1.length+1;i++)
                for(int j=1;j<nums2.length+1;j++){
                    if(nums1[i-1]==nums2[j-1])
                    {
                        dp[i][j]=dp[i-1][j-1]+1;
                        Result=Math.max(Result,dp[i][j]);
                    }
                }
            return Result;
    
        }