算法-动态规划/滑动窗口-最长重复子数组

1 概述

1.1 题目出处

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

1.2 题目描述

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

2 动态规划

2.1 思路

这个首先肯定想到的是循环，但是很难解决，不可能每个遍历一个数组的每个数又拿去到另一个数组遍历吧，这样时间复杂度直奔O(N^3)去了。

所以想想，是不是可以是父问题和子问题，貌似靠谱，那就试试动态规划了：

如果dp[i][j] 表示取A[i]结尾，B[j]结尾的子数组的最长重复子数组长度，则无法推到dp[i][j]和dp[i-1][j-1]的关系，因为无法确定到底是不是以A[i]B[j]作为最长重复子数组的一部分所以我们简单考虑，dp[i][j] 表示取A[i]结尾，B[j]结尾的子数组作为最长重复子数组时的最长重复子数组长度，则 ： 如果A[i] = B[j]，则dp[i][j] = dp[i-1][j-1] + 1否则 dp[i][j] = 0同时，我们在遍历过程中记录dp[i][j]最大值作为结果

所以，用动态规划的时候最重要的就是想清楚到底dp[i]表示什么才能方便找到与dp[i-1]的关系，如果一种想不通必须立刻转换思路，否则会导致你陷进去，时间耗光了却找不到答案！

2.2 代码

class Solution { public int findLength(int[] A, int[] B) { int minL = A.length < B.length ? A.length : B.length; // 如果dp[i][j] 表示取A[i]结尾，B[j]结尾的子数组的最长重复子数组长度，则无法推到dp[i][j]和dp[i-1][j-1]的关系 // 因为无法确定到底是不是以A[i]B[j]作为最长重复子数组的一部分 // 所以我们简单考虑，dp[i][j] 表示取A[i]结尾，B[j]结尾的子数组作为最长重复子数组时的最长重复子数组长度 // 则 如果A[i] = B[j]，则dp[i][j] = dp[i-1][j-1] + 1 // 否则 dp[i][j] = 0 // 同时，我们在遍历过程中记录dp[i][j]最大值作为结果 // 这里要注意，因为我们需要从A[0]和B[0]开始判断， // 但有需要找dp[i][j]和dp[i-1][j-1]的关系 // 所以我们将dp最大值设为dp[A.length][B.length] int[][] dp = new int[A.length + 1][B.length + 1]; int result = 0; for(int i = 1; i <= A.length; i++){ for(int j = 1; j <= B.length; j++){ if(A[i - 1] == B[j - 1]){ dp[i][j] = dp[i-1][j-1] + 1; result = Math.max(dp[i][j], result); } } } return result; } }

2.3 时间复杂度

O(m * n)

2.4 空间复杂度

O(m*n)

3 滑动窗口

3.1 思路

想想成两把尺子，拿一把尺子A从尺子B上方滑过，每次就拿B尺子的首元素和上方位置的A元素开始往后比。

思路动图详见滑动窗口解法

3.2 代码

3.3 时间复杂度

3.4 空间复杂度

O(m*n)