718. 最长重复子数组

给两个整数数组 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

动态规划-数组递推-倒序遍历

dp[i][j] 表示以 A[i] 和 B[j] 为起点的最长公共子数组的长度，两层for循环遍历两个数组，对数组A中的每个元素， 检查B中每个元素是否和它相等，如果相等，则dp[i][j] 等于 dp[i + 1][j + 1] + 1，否则dp[i][j]=0。 因为dp[i][j]依赖于dp[i+1][j+1]，所以我们要倒序遍历。

class Solution {
    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length; // 获取数组 A 和 B 的长度
        int[][] dp = new int[n + 1][m + 1]; // dp[i][j] 表示以 A[i] 和 B[j] 为起点的最长公共子数组的长度
        int ans = 0; // 变量 ans 用于记录最长公共子数组的长度

        // 从后往前遍历数组 A 和 B
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                // 如果 A[i] 和 B[j] 相等，则 dp[i][j] 等于 dp[i + 1][j + 1] + 1
                // 否则 dp[i][j] 等于 0
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                // 更新 ans 的值
                ans = Math.max(ans, dp[i][j]);
            }
        }

        return ans; // 返回最长公共子数组的长度
    }
}

• 时间复杂度： $O(N \times M)$ 。
• 空间复杂度： $O(N \times M)$ 。

N 表示数组 A 的长度，M 表示数组 B 的长度。

空间复杂度还可以再优化，利用滚动数组可以优化到 $O(\min (N,M))$。

动态规划-数组递推-正序遍历

class Solution {
    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length; // 获取数组 A 和 B 的长度
        int[][] dp = new int[n + 1][m + 1]; // 创建二维数组 dp，用于存储最长公共子数组的长度。 dp[i][j] 表示以 A[i - 1] 和 B[j - 1] 为终点的最长公共子数组的长度。之所以多一维是为了避免转移方程中的索引溢出。
        int ans = 0; // 变量 ans 用于记录最长公共子数组的长度

        // 从前往后遍历数组 A 和 B
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 如果 A[i-1] 和 B[j-1] 相等，则 dp[i][j] 等于 dp[i - 1][j - 1] + 1
                // 否则 dp[i][j] 等于 0。这里i和j指的是个数，不是索引，也可以改为索引。
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 重点。子数组必须以A[i-1]和B[j-1]结尾，子数组意味着连续，只有以当前元素结尾才能和后面的连起来。
                    dp[i][j] = 0;
                }
                // 更新 ans 的值
                ans = Math.max(ans, dp[i][j]);
            }
        }

        return ans; // 返回最长公共子数组的长度
    }
}

• 时间复杂度： $O(N \times M)$ 。
• 空间复杂度： $O(N \times M)$ 。

N 表示数组 A 的长度，M 表示数组 B 的长度。

空间复杂度还可以再优化，利用滚动数组可以优化到 $O(\min (N,M))$。

滑动窗口，穷举

遍历数组 A，从每个索引 i 开始和 B 的前缀比较，计算从 A[i] 和 B[0] 开始的最长公共子数组的长度maxLength(A, B, i, 0, len)，其中len是可以比较的最长长度。maxLength会从0到len遍历，如果两个数组中当前索引的元素相等，则长度加一，否则长度置为0，然后记录最大长度。

class Solution {
    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length; // 获取数组 A 和 B 的长度
        int ret = 0; // 记录最长公共子数组的长度

        // 遍历数组 A，从每个索引 i 开始和 B 的前缀比较
        for (int i = 0; i < n; i++) {
            // 计算可以比较的最长长度 len
            int len = Math.min(m, n - i);
            // 计算从 A[i] 和 B[0] 开始的最长公共子数组的长度
            int maxlen = maxLength(A, B, i, 0, len);
            // 更新结果
            ret = Math.max(ret, maxlen);
        }

        // 遍历数组 B，从每个索引 i 开始和 A 的前缀比较
        for (int i = 0; i < m; i++) {
            // 计算可以比较的最长长度 len
            int len = Math.min(n, m - i);
            // 计算从 A[0] 和 B[i] 开始的最长公共子数组的长度
            int maxlen = maxLength(A, B, 0, i, len);
            // 更新结果
            ret = Math.max(ret, maxlen);
        }

        return ret; // 返回最长公共子数组的长度
    }

    // 计算从 A[addA] 和 B[addB] 开始的最长公共子数组的长度
    public int maxLength(int[] A, int[] B, int addA, int addB, int len) {
        int ret = 0, k = 0; // ret 记录最大长度，k 记录当前长度
        for (int i = 0; i < len; i++) {
            if (A[addA + i] == B[addB + i]) {
                k++; // 如果当前元素相等，当前长度加1
            } else {
                k = 0; // 否则，重置当前长度
            }
            ret = Math.max(ret, k); // 更新最大长度
        }
        
        return ret; // 返回最大长度
    }
}

• 时间复杂度： $O((N+M) \times \min (N, M))$ 。
• 空间复杂度： $O(1)$ 。
• $N$ 表示数组 $A$ 的长度，M 表示数组 $B$ 的长度。