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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

DP思路比较简单，表示以nums1[i]和nums2[j]结尾（必须包含nums1[i]和nums2[j]）的最长公共子数组长度。如果nums1[i]==nums2[j]，那么，否则等于0。

也可以使用滑窗解决，想象两列车相向开过，最长公共部分一定出现在某一时刻。具体实现上，固定其中一个数组，移动另一个数组的起始下标到固定数组的起始位置，然后进行比对，更新最长的公共长度。

代码

DP

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}

滑窗

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int len = Math.min(m, n - i);
            int res = maxLength(nums1, nums2, i, 0, len);
            ans = Math.max(ans, res);
        }
        for (int i = 0; i < m; ++i) {
            int len = Math.min(n, m - i);
            int res = maxLength(nums1, nums2, 0, i, len);
            ans = Math.max(ans, res);
        }
        return ans;
    }
    // 从A数组的startA和B数组的startB位置开始比对len个长度，返回最长的公共子数组长度
    private int maxLength(int[] nums1, int[] nums2, int startA, int startB, int len) {
        int res = 0;
        int cnt = 0;
        for (int i = 0; i < len; ++i) {
            if (nums1[startA + i] == nums2[startB + i]) {
                cnt++;
            } else {
                cnt = 0;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}

更简洁的滑窗

参考「这里」，学习一下，很赞。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int ans = 0;
        // 枚举nums1起始下标和nums2的差值
        for (int delta = -n; delta < m; delta++) {
            int cnt = 0;
            // 通过 0 <= i < n && 0 <= i + delta < m 可以得到Math.max(-delta, 0) <= i < Math.min(n, m - delta)
            for (int i = Math.max(-delta, 0); i < Math.min(n, m - delta); i++) {
                if (nums1[i] == nums2[i + delta]) {
                    cnt++;
                } else {
                    cnt = 0;
                }
                ans = Math.max(ans, cnt);
            }
        }
        return ans;
    }
}