每日一解 最长重复子数组

题目 最长重复子数组

给两个整数数组 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

思路

本题有两个典型的思路，一个是我依然不太擅长的动态规划，另一个则是还好一些的滑动窗口解法。 因为我不太擅长动归的缘故，所以尽量练习一下动归的解法。 这次的动归如果不是参考了一下官解，感觉我也得不出正确的思路。关键在于将重复子数组转化为最长公共前缀，从末尾的字母开始进行比较。简单来说，就是A数组中第i个数字，如果与B数组中的第j个数字相同的话，那么dp_map[i] [j]的值应当是dp_map[i +1][j + 1]的值 + 1。我这里采用自己设计的一个输入例子演示一下dp_map的值： 输入： A：[2, 3, 9, 2, 4, 3, 7] B：[7, 9, 2, 4, 3, 3] 那么这样安排会得到的dp_map为：

i0123456额外j000000010100400000210030000300002000401000100501000100额外00000000

那么按照这个思路代码实现一下：

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int row = A.size() + 1; int vertical = B.size() + 1; vector<vector<int>> dp_map(row, vector<int>(vertical, 0));//这里很关键，把初始二维数组全部置0. int answer = 0; for (int i = row - 2; i >= 0; i--) { for (int j = vertical - 2; j >= 0; j--) { if (A[i] == B[j]) { dp_map[i][j] = dp_map[i + 1][j + 1] + 1; if (dp_map[i][j] > answer) { answer = dp_map[i][j]; } } } } return answer; } };

动归的时间结果还算可以，但是空间结果不怎么尽如人意。那么采用滑动窗口方法可以直接将空间复杂度降低为O(1)。 这里同样用表格大概讲一下滑动窗口方法的内容，依然使用刚才的例子：

A2392437B792433

此时滑动窗口就是中间的7，那么得到此时最长重复子数组为1. 然后继续滑动：

A2392437B792433

此时滑动窗口为中间的2格，此时最长重复子数组为0. 再次滑动：

A2392437B792433

如此往复滑动，直到如下的情况：

A2392437B792433

这种方法的代码实现为：

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int A_length = A.size(), B_length = B.size(); int short_length, long_length; int answer = 0; vector<int> A_array; if (A_length < B_length) { short_length = A_length; long_length = B_length; } else { A_array = B; B = A; A = A_array; short_length = B_length; long_length = A_length; } for (int i = 0; i < short_length; i++) { int similarity = 0; for (int j = 0; j <= i; j++) { if (A[j] != B[long_length - i + j - 1]) { similarity = 0; continue; } similarity++; if (similarity > answer) { answer = similarity; } } } for (int i = long_length - short_length - 1; i >= 0; i--) { int similarity = 0; for (int j = 0; j < short_length; j++) { if (A[j] != B[i + j]) { similarity = 0; continue; } similarity++; if (similarity > answer) { answer = similarity; } } } for (int i = 0; i < short_length; i++) { int similarity = 0; for (int j = 0; j <= i; j++) { if (A[short_length - i + j - 1] != B[j]) { similarity = 0; continue; } similarity++; if (similarity > answer) { answer = similarity; } } } return answer; } };

这种类似“滑动窗口”的方法，时间和空间结果都要好很多。