每日题解:LeetCode 718. 最长重复子数组

题目地址 个人博客地址

题目描述

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

示例： 输入： 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

解法

JAVA

class Solution { public int findLength(int[] A, int[] B) { int lenA = A.length; int lenB = B.length; int ans = 0; for (int i = 0; i < lenA; ++i) { int len = Math.min(lenB, lenA - i); int maxLen = finMaxLen(A, B, i, 0, len); ans = Math.max(ans, maxLen); } for (int i = 0; i < lenB; ++i) { int len = Math.min(lenA, lenB - i); int maxLen = finMaxLen(A, B, 0, i, len); ans = Math.max(ans, maxLen); } return ans; } private int finMaxLen(int[] A, int[] B, int addA, int addB, int len) { int ret = 0, k = 0; for (int i = 0; i < len; i++) { if (A[addA + i] == B[addB + i]) { k++; } else { k = 0; } ret = Math.max(ret, k); } return ret; } }

CPP

class Solution { public: static int findLength(vector<int> &A, vector<int> &B) { //DP[i][j] int ans = 0; int lenA = A.size(); int lenB = B.size(); vector<vector<int>> dp(lenA + 1, vector<int>(lenB + 1, 0)); for (int i = lenA - 1; i >= 0; i--) { for (int j = lenB - 1; j >= 0; j--) { dp[i][j]=A[i]==B[j]?dp[i+1][j+1]+1:0; ans=max(ans, dp[i][j]); } } return ans; } };

解题思路

最简单的写法是三层循环，逐步对比字符是否相等，然后往后遍历，

for(){ for(){ while(){ } } }

但是这题的测试用例会出现超时的问题，所以就需要减少循环的次数

滑动窗口

出处：小马的笔记

我觉的这个gif能很好的表示滑动窗口的做法 1.先固定A，移动 B，逐个寻找公共子数组中的长度 2.反之，固定B，移动A，寻找公共子数组中的长度 3.对比寻找处最大的公共子数组长度

for (int i = 0; i < lenA; ++i) { int len = Math.min(lenB, lenA - i); //先固定B的位置，即B数组的下标为0 int maxLen = finMaxLen(A, B, i, 0, len); ans = Math.max(ans, maxLen); } /** * Solution:: finMaxLen * <p>寻找len长度内，两个数组的最长公共子数组/p> * <p>HISTORY: 2020/7/1 liuha : Created.</p> * @param A A数组 * @param B B数组 * @param addA A数组的滑动开始的下标，0下标表示当前数组为固定的数组 * @param addB B数组的滑动开始的下标，0下标表示当前数组为固定的数组 * @param len * @return 最长公共子数组的长度长度 */ private int finMaxLen(int[] A, int[] B, int addA, int addB, int len) { int ret = 0, k = 0; for (int i = 0; i < len; i++) { if (A[addA + i] == B[addB + i]) { k++; } else { k = 0; } ret = Math.max(ret, k); } return ret; }

这个思路又借鉴官方的写法，我觉得官方的写法更优雅，这里将时间复杂度降到了O((N+M)×min(N,M))， 但我们遍历完A数组别忘记，还要固定A数组，遍历B数组

for (int i = 0; i < lenB; ++i) { int len = Math.min(lenA, lenB - i); int maxLen = finMaxLen(A, B, 0, i, len); ans = Math.max(ans, maxLen); }

DP

我们假设dp[i][j] 表示 A[] 和 B[]的最长公共前缀，i,j分别是数组的下标，那么答案即为所有 dp[i][j] 中的最大值。 我们以示例

A: [1,2,3,2,1] B: [3,2,1,4,7]

如表格所示，我们需要的在坐标为 (0,2)(1,3)(2,4)

12321A数组3121111147B数组

存在的规律 1.下标存在dp[i][j]–>dp[i+1][j+1]->dp[i+2][j+2] 2.如图中箭头指向，当A[i]==B[j]时dp[i][j]=dp[i+1][j+1]+1，或者理解为A[i-1]==B[j-1]时dp[i][j]=dp[i-1][j-1]+1， 那就可以整理处DP的状态公式了 dp[i][j]=dp[i+1][j+1]+1 if(A[i]==B[j]) 由于dp[i][j]从``dp[i+1][j+1]得到，所以我们要反过来遍历数组

for (int i = lenA - 1; i >= 0; i--) { for (int j = lenB - 1; j >= 0; j--) { dp[i][j]=A[i]==B[j]?dp[i+1][j+1]+1:0; ans=max(ans, dp[i][j]); } }

或者使用另一个状态公式遍历

for (int i = 1; i <= lenA; i++) { for (int j = 1; j <= lenB; j++) { if (A[i - 1] == B[j - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; ans = max(ans, dp[i][j]); } } }