718. 最长重复子数组

LeetCode_718

题目描述

解法一：使用动态规划

1. 首先需要说明的是，这题和最长公共子序列是不同的，子序列并没有要求说是连续的，而连续数组则要求是连续的。
2. 首先定义dp[i][j]表示为A[i:]和B[j:]的最长公共前缀。
3. dp[i][j]可以从dp[i+1][j+1]转移而来。

class Solution {
    public int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int[][] dp = new int[m+1][n+1];//dp[i][j]表示从i开始的A的子串和从j开始的B的子串的最长公共前缀
                                        //dp[i][j]可以从dp[i+1][j+1]转移而来
        int maxlen = 0;
        for(int i=m-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                if(A[i] == B[j]){
                    dp[i][j] = dp[i+1][j+1] + 1;
                }else{
                    dp[i][j] = 0;
                }
                maxlen = Math.max(maxlen, dp[i][j]);
            }
        }
        return maxlen;
    }
}

方法二：滑动窗口

class Solution {
    public int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int max = 0;
        for(int i=0; i<n; i++){//固定B数组，移动A数组
            int k = Math.min(m, n - i);
            int res = maxLength(A, B, i, 0, k);
            max = Math.max(max, res);
        }
        for(int i=0; i<m; i++){//固定A数组，移动B数组
            int k = Math.min(n, m - i);
            int res = maxLength(A, B, 0, i, k);
            max = Math.max(max, res);
        }
        return max;
    }
    //
    public int maxLength(int[] numa, int[] numb, int a, int b, int k){//k表示滑动窗口的长度
        int max = 0;
        int ans = 0;
        for(int i=0; i<k; i++){
            if(numa[a + i] == numb[b + i])
                ans++;
            else{
                ans = 0;
            }
            max = Math.max(max, ans);
        }
        return max;
    }
}