力扣刷题笔记 718. 最长重复子数组 C#

题目如下

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

示例 1:

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

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

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

最初实现使用暴力解法，3次循环，预料之中，提交结果超时，以下贴出代码，不做赘述。

public class Solution { public int FindLength(int[] A, int[] B) { int count = 0; for (int i = 0; i < A.Length; i++) { for (int j = 0; j < B.Length; j++) { int k = 0; while(i + k < A.Length && j + k < B.Length && A[i + k] == B[j + k]) { k++; } if (k > count) { count = k; } } } return count; } }

解题失败后看官方解题思路，一共提出三种解法：

动态规划滑动窗口二分查找 + 哈希

解法3没有看懂，也没有尝试编写代码，以下自我回顾前两种解法，诉述可能有误，如有发现还请评论指出。

1.动态规划

假设数组为 A ,B，若 A[i] == B[j]，将 A[i] 以及 A[i] 之后的元素集合视作 A[i] 子数组，记作A[i']，B[j'] 同理。

则以 A[i] 和 B[j] 开始的对比结果即为，A[i'] 和 B[j'] 从 0 开始最长的相同元素长度。

以此理解，因为A[i] == B[j]，所以对比结果即为A[i'] 和 B[j'] 从 1 开始最长的相同元素长度 + 1，即以 A[i+1] 和 B[j + 1] 开始的对比结果。

所有的对比结果集合长度应为 数组 A 长度 * 数组 B 长度，故取一个二维数组 record 记录所有对比结果。

综上，record[i][j] = record[i+1][j+1]。

由于需要先获得向后的对比结果，所以对两个数组逆序遍历。

解法时间复杂度为两层逆序遍历 O(M*N)，空间复杂度为记录结果的二维数组 O(M*N)，M、N分别表示两个数组长度。

以下为代码：

public class Solution { public int FindLength(int[] A, int[] B) { int[,] temp = new int[A.Length,B.Length]; int ans = 0; for(int i = A.Length - 1; i >= 0;i--) { for(int j = B.Length - 1;j >= 0;j--) { if (i == A.Length - 1 || j == B.Length - 1) { temp[i,j] = A[i] == B[j]? 1 : 0; } else { temp[i,j] = A[i] == B[j]? temp[i + 1,j + 1] + 1 :0; } ans = Math.Max(ans,temp[i,j]); } } return ans; } }

2.滑动窗口

最长子数组的起始点位置在两个数组中未必一致，故对比过程需要逐个遍历不同的起始位置。

由此，我们可以将两个数组以不同的起始位置对齐后开始比较，如，数组 A 从下标 1 开始逐格数组 B 从 0 开始的元素。

遍历 A 的每个下标作为起始位置对齐 B 的下标 0，再同理遍历 B 的每个标，即可获得所有起始点的对齐结果。

在以上的每次遍历当中，逐个向后对比字符是否相等，通过计数器记录，如果不相等则对比当前结果，然后中断重新记录。

对两个数组遍历结束，得出结果。

解法时间复杂度为 A B 两个数组分别遍历（M+N)，乘以内层遍历的下标最大保护min(N,M)， O((M+N)*min(N,M))。由于并未使用辅助集合，空间复杂度为O(1)。

此处引用力扣该题官方题解所用配图。

以下为代码：

public class Solution { public int FindLength(int[] A, int[] B) { int ans = 0; for (int i = 0;i < A.Length;i++) { int len = Math.Min(B.Length, A.Length - i); int k = CheckLength(A,B,i,0,len); ans = Math.Max(ans,k); } for (int i = 0;i < B.Length;i++) { int len = Math.Min(A.Length, B.Length - i); int k = CheckLength(A,B,0,i,len); ans = Math.Max(ans,k); } return ans; } private int CheckLength(int[] A, int[] B,int baseA,int baseB, int len) { int ans = 0; int k = 0; for (int i = 0; i < len; i++) { if (A[baseA + i] == B[baseB + i]) { k++; } else { ans = Math.Max(ans, k); k = 0; } } ans = Math.Max(ans, k); return ans; } }