718. 最长重复子数组动态规划

718. 最长重复子数组

难度：中等 题目描述 解题思路

1、动态规划

长得就像动态规划的题，但是还是不是自己想出来的 设置状态dp[i][j]代表以A[i-1]与B[j-1]结尾的公共字串的长度 初始的时候是0，循环遍历填表，记录全局最大值 比如A: [1,2,3,2,1] B: [3,2,1,4,7] 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 3 0 0

/* * 718. 最长重复子数组 * 2020/7/1 动态规划 * dp[i][j]代表以A[i-1]与B[j-1]结尾的公共字串的长度 */ public static int findLength(int[] A, int[] B) { int m = A.length,n = B.length; int[][] dp = new int[m+1][n+1]; int max = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if(A[i] == B[j]) { dp[i+1][j+1] = dp[i][j] + 1; max = Math.max(max, dp[i+1][j+1]); } } } return max; }

2、滑动窗口法 很绝

就是一直移动数组对齐的位置，计算重叠部分相同的最大值

public int findLength(int[] A, int[] B) { int m = A.length,n = B.length; int max = 0,total = m + n - 1; int aStart = 0; int bStart = 0; int len = 0; for (int i = 0; i < total; i++) { if(i < m) { aStart = 0; len = i+1; bStart = n-len; }else { bStart = 0; aStart = i-m+1; len = Math.min(n - aStart, m); if(len < max) //如果剩下重叠区间长度都小于已有的max return max; } max = Math.max(max, maxLength(A,B,aStart,bStart,len)); } return max; } //计算A和B在上面图中红色框内的最大长度 public int maxLength(int[] A, int[] B, int aStart, int bStart, int len) { int max = 0, count = 0; for (int i = 0; i < len; i++) { if (A[aStart + i] == B[bStart + i]) { count++; max = Math.max(max, count); } else { count = 0; } } return max; }