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

【问题描述】[中等]

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

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. 动态规划

第 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)

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. 滑动窗口

时间复杂度：O((N+M)×min(N,M)) 空间复杂度：O(1)

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/