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

解法

1. 暴力遍历

判断 nums2 中以每个元素为结尾的子数组在 nums1 中的最大长度，数组太长时会超时。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length];
        int maxLen = 0;
        for (int i = 0; i < nums2.length; i++) {
            for (int j = 0; j < nums1.length; j++) {
                if (nums1[j] == nums2[i]) {
                    // 当前字符匹配的话最小长度为1
                    int len = 1;
                    if (i > 0 && j > 0 && dp[i - 1] >= 0) {
                        // 向前匹配子数组
                        for (; len <= dp[i - 1] && j >= len && i >= len; len++) {
                            if (nums1[j - len] != nums2[i - len]) {
                                break;
                            }
                        }
                    }
                    dp[i] = Math.max(len, dp[i]);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

2. 半动态规划

上面的暴力解法每次都要重新匹配下以当前字符结尾的最大子数组长度，如果可以用保存下前一位数组的长度位置，那么只要判断下当前元素在目标数组中是否存在且和前一个元素相邻那么就直接在前一位元素的最长子数组的长度加一即可。所以需要保存两个数据：匹配子数组长度和匹配的位置或者匹配的起始和结束位置也可以。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // dp[i][0]: 匹配位置，dp[i][1]: 匹配长度
        int[][] dp = new int[nums2.length][2];
        int maxLen = 0;
        for (int i = 0; i < nums2.length; i++) {
            for (int j = 0; j < nums1.length; j++) {
                if (nums1[j] == nums2[i]) {
                    if (i == 0) {
                        dp[i][0] = j;
                        dp[i][1] = 1;
                        break;
                    }
                    // 当前匹配位置与前一匹配位置相邻，直接 +1
                    if (j == dp[i - 1][0] + 1) {
                        dp[i][0] = j;
                        dp[i][1] = dp[i - 1][1] + 1;
                        break;
                    }
                    // 当前匹配位置与前一匹配位置不相邻，无法使用dp数组判断，需要遍历匹配判断子数组长度
                    int len = 1;
                    // 向前匹配子数组最大长度
                    for (; j >= len && i >= len; len++) {
                        if (nums1[j - len] != nums2[i - len]) {
                            break;
                        }
                    }
                    // 更新匹配位置与匹配长度
                    if (len > dp[i][1]) {
                        dp[i][0] = j;
                        dp[i][1] = len;
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[i][1]);
        }
        return maxLen;
    }
}

3. 动态规划

上面这种方式可以节约一部分判断，但是并不能完全依赖 dp 数组，一部分还需要遍历判断，尤其在不相邻情况比较多是时间复杂度也会很高。只有在当前匹配位置与前一匹配位置相邻时可以通过 dp 数据进行优化，如果不相邻则只能手动判断，如果可以使用 dp 数组记录每一个位置前一位的匹配情况就可以完全避免手动判断。

1. 定义 DP 数组

如下图，设 dp[i][j] 为以 A[i] 结尾和 B[j] 结尾的最长公共子数组长度，这样这个二维数组就可以存储 A、B 中以每个位置结尾的最长公共子数组长度。

2. 状态转移方程

if (A[i] != B[j]) dp[i][j] = 0

if (A[i] == B[j]) dp[i][j] = dp[i - 1][j - 1] + 1

3. DP 数组初始化

由状态转移方程可以看出来 dp 数组中的值只与其左上角的值有关，所以只需要初始化第一行和第一列就可以了。

// 初始化第一行
for (int i = 0; i < dp[0].length; i++) {
    if (nums1[0] == nums2[i]) {
        dp[0][i] = 1;
        maxLen = 1;
    }
}
// 初始化第一列
for (int i = 0; i < dp.length; i++) {
    if (nums2[0] == nums1[i]) {
        dp[i][0] = 1;
        maxLen = 1;
    }
}

此时初始化比较麻烦，且还很容易忘记维护 maxLen，所以可以将数组扩大一圈，dp[i][j] 为以 A[i - 1] 结尾和 B[j - 1] 结尾的最长公共子数组长度，那么第一行和第一列只需要填充 0 就可以了，避免了初始化的麻烦。

4. 最终代码

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // dp[i][j] 为以 nums1[i - 1] 结尾和 nums2[j - 1] 结尾的最长公共子数组长度
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int maxLen = 0;
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen;
    }
}

5. 数组压缩

由于 dp[i][j] 只与其左上角的值有关，可以只使用一维数组来进行维护，遍历 nums2 的时候要倒序，避免影响 dp[i - 1][j - 1] 的值。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // dp[i][j] 为以 nums1[i - 1] 结尾和 nums2[j - 1] 结尾的最长公共子数组长度
        int[] dp = new int[nums2.length + 1];
        int maxLen = 0;
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = nums2.length; j > 0; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[j]);
                } else {
                    // 注意不匹配时要更新为 0
                    dp[j] = 0;
                }
            }
        }
        return maxLen;
    }
}