718. 最长重复子数组

题目描述

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

输入输出

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

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

基本思路

动态规划：令dp[i][j]为nums1[i:]和nums2[j:]的最长公共前缀 那么答案为dp[i][j]的最大值

如果nums1[i] == nums2[j] 则dp[i][j] = dp[i+1][j+1] + 1 否则dp[i][j] = 0

考虑到dp[i][j]由dp[i+1][j+1]得来所以需要倒过来计算

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1+1][len2+1];
        int ans = 0;
        for(int i = len1-1; i >= 0; i--){
            for(int j = len2-1; j >= 0; j--){
                dp[i][j] = nums1[i] == nums2[j] ? dp[i+1][j+1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]); 
            }
        }
        return ans;
    }
}