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

浅浅的花香味﹌ 2023-02-21 14:19 1阅读 0赞

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

# 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)][O_m_n]  
O(m \* n)

## 2.4 空间复杂度 ##

O(m\*n)

# 3 滑动窗口 #

## 3.1 思路 ##

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

思路动图详见[滑动窗口解法][Link 1]

## 3.2 代码 ##

## 3.3 时间复杂度 ##

## 3.4 空间复杂度 ##

O(m\*n)

[O_m_n]: https://img-blog.csdnimg.cn/20200701103304639.png
[Link 1]: https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/wu-li-jie-fa-by-stg-2/