[718. 最长重复子数组]

难度 中等

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

示例 1:

输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。

说明:

1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray

解法一：动态规划

dp[i][j] 表示 A 中前 i 个元素 和 B 中前 j 个元素范围内的重复子数组的长度，状态转移方程为

dp[i][j] = 0，如果 i == 0 || j == 0 || A[i - 1] == B[j - 1]dp[i][j] = dp[i - 1][j - 1] + 1 ， 如果 i ！= 0 && j ！= 0 && A[i - 1] == B[j - 1] 例如：例如：A: [1,2,3,2,1] B: [3,2,1,4,7] class Solution { public int findLength(int[] A, int[] B) { int lenA = A.length, lenB = B.length; int ans = 0; int[][] dp = new int[lenA + 1][lenB + 1]; for(int i = 0; i <= lenA; i++){ for(int j = 0; j <= lenB; j++){ if(i == 0 || j == 0){ dp[i][j] = 0; continue; } //如果 A 中的 第 i 个字符与 B 中的第 j 个字符相等， 则 dp[i][j] = dp[i - 1][j - 1] + 1 if(A[i - 1] == B[j - 1]){ dp[i][j] = dp[i - 1][j - 1] + 1; ans = Math.max(ans, dp[i][j]); }else{ dp[i][j] = 0; } } } return ans; } }

复杂度分析

时间复杂度：O(N×M)。空间复杂度：O(N×M)。 N 和 M 分别为数组 A 和 B 的长度。

解法二：滑动窗口

例：A = [3, 6, 1, 2, 4], B = [7, 1, 2, 9] ，它们的最长重复子数组是 [1, 2]，但在 A 与 B 中的开始位置不同导致我们需要比较多次。如何能够将 A 和 B 按照下面的方式进行对其则只需要进行一次遍历。

//A 不变，B 的第 1 个元素和 A 的第 2 个元素对其 A = [3, 6, 1, 2, 4] B = [7, 1, 2, 9] ↑ ↑

对其方式：

A 不变，B 的首元素与 A 中的某个元素对齐。B 不变，A 的首元素与 B 中的某个元素对齐。 class Solution { public int findLength(int[] A, int[] B) { int lenA = A.length, lenB = B.length; int ans = 0; //A 不变，B 的首元素与 A 中的某个元素对齐 for (int i = 0; i < lenB; i++) { int len = Math.min(lenB, lenB - i); int maxlen = maxLength(A, B, 0, i, len); ans = Math.max(ans, maxlen); } //B 不变，A 的首元素与 B 中的某个元素对齐 for (int i = 0; i < lenA; i++) { int len = Math.min(lenB, lenA - i); int maxlen = maxLength(A, B, i, 0, len); ans = Math.max(ans, maxlen); } return ans; } public int maxLength(int[] A, int[] B, int addA, int addB, int len) { int ans = 0, k = 0; for (int i = 0; i < len; i++) { if (A[addA + i] == B[addB + i]) { k++; } else { k = 0; } ans = Math.max(ans, k); } return ans; } }

复杂度分析

时间复杂度： O((N + M)空间复杂度： O(1)