LeetCode_动态规划_中等_718.最长重复子数组

旧城等待， 2023-10-06 23:20 44阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给两个整数数组 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 <= nums1.length, nums2.length <= 1000  
0 <= nums1\[i\], nums2\[i\] <= 100

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray

## 2.思路 ##

（1）暴力穷举法  
该方法比较容易想到，即**穷举数组 nums1 中的起始位置 i 和数组 nums2 中的起始位置 j，然后计算 nums1\[i…length1 - 1\] 和 nums2\[j…length2 - 1\] 的最长公共前缀 k，在计算的过程中用变量 res 记录 k 的最大值**，待穷举结束后返回 res 即可。该方法的时间复杂度为O(n3)。

（2）动态规划  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int findLength(int[] nums1, int[] nums2) {
        
            int res = 0;
            int length1 = nums1.length;
            int length2 = nums2.length;
            for (int i = 0; i < length1; i++) {
        
                for (int j = 0; j < length2; j++) {
        
                    int k = 0;
                    while (i + k < length1 && j + k <length2 && nums1[i + k] == nums2[j + k]) {
        
                        k++;
                    }
                    res = Math.max(res, k);
                }
            }
            return res;
        }
    }

//思路2————动态规划
    class Solution {
        
        public int findLength(int[] nums1, int[] nums2) {
        
            int res = 0;
            int length1 = nums1.length;
            int length2 = nums2.length;
            //dp[i][j] 表示 nums1[i...length1 - 1] 和 nums2[j...length2 - 1] 的最长公共前缀
            int[][] dp = new int[length1 + 1][length2 + 1];
            for (int i = length1 - 1; i >= 0; i--) {
        
                for (int j = length2 - 1; j >=0; j--) {
        
                    dp[i][j] = (nums1[i] == nums2[j]) ? dp[i + 1][j + 1] + 1 : 0;
                    res = Math.max(dp[i][j], res);
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/