[Leetcode][第718题][JAVA][最长重复子数组][动态规划][滑动窗口][暴力]

桃扇骨 2023-02-21 14:19 6阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

###### 1. 暴力法 ######

**时间复杂度：O(N^3) 空间复杂度：O(1)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

public int findLength1(int[] numa, int[] numb) { 
        	if(numa == null || numb ==null){ 
        		return 0;
        	}
        	int max = 0;
        	int aLen = numa.length, bLen = numb.length;
        	
        	int aIndex, bIndex, sameLen;
        	for(int i=0; i<aLen; i++){ 
        		for(int j=0; j<bLen; j++){ 
        			aIndex = i;
        			bIndex = j;
        			sameLen = 0;
        			while(aIndex<aLen && bIndex<bLen && numa[aIndex]==numb[bIndex] ){ 
        				sameLen++;
        				aIndex++;
        				bIndex++;
        			}
        			if(max < sameLen){ 
        				max = sameLen;
        			}
        		}
        	}
        	return max;
        }

###### 2. 动态规划 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
第 1 步：设计状态  
int\[\]\[\] dp 表示 A\[i:\] 和 B\[j:\] 的最长公共前缀  
第 2 步：状态转移方程  
如果 A\[i\] == B\[j\]，那么 dp\[i\]\[j\] = dp\[i + 1\]\[j + 1\] + 1，否则 dp\[i\]\[j\] = 0。  
第 3 步：考虑初始化  
int\[\]\[\] dp = new int\[n + 1\]\[m + 1\];  
第 4 步：考虑输出 max  
第 5 步：考虑是否可以状态压缩 暂时不考虑

**时间复杂度：O(N×M) 空间复杂度：O(N×M)**  
![在这里插入图片描述][20200701103822316.png]

class Solution { 
        public int findLength(int[] A, int[] B) { 
            int n = A.length, m = B.length;
            int[][] dp = new int[n + 1][m + 1];
            int ans = 0;
            for (int i = n - 1; i >= 0; i--) { 
                for (int j = m - 1; j >= 0; j--) { 
                    dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
            return ans;
        }
    }

public int findLength(int[] A, int[] B) { 
            int lenA = A.length;
            int lenB = B.length;
            int[][] dp = new int[lenA][lenB];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < lenA; i++) { 
                for (int j = 0; j < lenB; j++) { 
                    if (A[i] == B[j]){ 
                        if (i > 0 && j > 0){ 
                            dp[i][j] =  dp[i - 1][j - 1] + 1;
                        }else{ 
                            dp[i][j] = 1;
                        }
                    }
                    max = Math.max(max,dp[i][j]);
                }
            }
            return max;
        }

###### 3. 滑动窗口 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
**时间复杂度：O((N+M)×min(N,M)) 空间复杂度：O(1)**  
![在这里插入图片描述][20200701104908806.png]

class Solution { 
        public int findLength(int[] A, int[] B) { 
            int n = A.length, m = B.length;
            int ret = 0;
            for (int i = 0; i < n; i++) { 
                int len = Math.min(m, n - i);
                int maxlen = maxLength(A, B, i, 0, len);
                ret = Math.max(ret, maxlen);
            }
            for (int i = 0; i < m; i++) { 
                int len = Math.min(n, m - i);
                int maxlen = maxLength(A, B, 0, i, len);
                ret = Math.max(ret, maxlen);
            }
            return ret;
        }
    
        public int maxLength(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;
        }
    }

#### 【总结】 ####

###### 1. 暴力法 注意边界问题 ######

###### 2.动态规划 做到前四就不错啦 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 3.滑动窗口 还可以是两个块之间对比使用 之前都是用双指针滑的 ######

转载链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200701103250664.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020070110344353.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200701103822316.png]: https://img-blog.csdnimg.cn/20200701103822316.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200701104613572.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200701104908806.png]: https://img-blog.csdnimg.cn/20200701104908806.png