718. 最长重复子数组

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

示例 1：

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

示例 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：以 nums[i] 和 nums[j] 为开头的最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length, res = 0;
        // f[i][j]: 以 nums[i] 和 nums[j] 为开头的最长公共前缀
        int f[][] = new int[m+1][n+1];
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (nums1[i] == nums2[j]) {
                    f[i][j] = f[i+1][j+1] + 1;
                    res = Math.max(res, f[i][j]);
                }
            }
        }
        return res;
    }
}

dp：以 nums[i] 和 nums[j] 为结尾的最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length, res = 0;
        // f[i][j]: 以 nums[i] 和 nums[j] 为结尾的最长公共前缀
        int f[][] = new int[m+1][n+1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (nums1[i] == nums2[j]) {
                    f[i+1][j+1] = f[i][j] + 1;
                    res = Math.max(res, f[i+1][j+1]);
                }
            }
        }
        return res;
    }
}

还有字符串哈希解法