最长重复子数组（暴力动态规划滑窗法）

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//三重for循环超时 public class Main { public static void main(String[] args) { int k = 4; // int[] A = {0,1,1,1,1}; int[] A = {1,2,3,2,1}; // int[] A = {0,0,0,0,0,0,1,0,0,0}; // int[] B = {1,0,1,0,1}; int[] B = {3,2,1,4,7}; // int[] B = {0,0,0,0,0,0,0,1,0,0}; System.out.println(findLength(A, B) ); } public static int findLength(int[] A, int[] B) { int ans = Integer.MIN_VALUE; int tmp = 0; for (int i=0; i<A.length; i++) { for (int j=0; j<B.length; j++) { tmp = 0; int k = i; for (int t = j; t<B.length; t++) { if (k < A.length) { if (A[k] == B[t]) { k++; tmp++; if (tmp > ans) { ans = tmp; } } else { tmp = 0; } } } } } if (ans == Integer.MIN_VALUE) { ans = 0; } return ans; } }

 

//暴力优化，卡时间过测试点 public class Main { public static void main(String[] args) { int k = 4; // int[] A = {0,1,1,1,1}; // int[] A = {1,2,3,2,1}; int[] A = {0,0,0,0,0,0,1,0,0,0}; // int[] B = {1,0,1,0,1}; // int[] B = {3,2,1,4,7}; int[] B = {0,0,0,0,0,0,0,1,0,0}; System.out.println(findLength(A, B) ); } public static int findLength(int[] A, int[] B) { int ans = Integer.MIN_VALUE; int tmp = 0; for (int i=0; i<A.length; i++) { for (int j=0; j<B.length; j++) { tmp = 0; if (A[i] == B[j]) { int k = i; int t = j; //优化 while (k < A.length && t < B.length && A[k] == B[t]) { k++; t++; tmp++; if (tmp > ans) { ans = tmp; } } } if (ans >= A.length-i) { //优化 return ans; } } } if (ans == Integer.MIN_VALUE) { ans = 0; } return ans; } } //DP动态规划 public class Main { public static void main(String[] args) { int k = 4; // int[] A = {0,1,1,1,1}; // int[] A = {1,2,3,2,1}; int[] A = {0,0,0,0,0,0,1,0,0,0}; // int[] B = {1,0,1,0,1}; // int[] B = {3,2,1,4,7}; int[] B = {0,0,0,0,0,0,0,1,0,0}; System.out.println(findLength(A, B) ); } public static int findLength(int[] A, int[] B) { int ans = 0; int dp[][] = new int[A.length+1][B.length+1]; 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; } ans = Math.max(ans, dp[i][j]); } } return ans; } } //滑窗法 public class Main { public static void main(String[] args) { int k = 4; // int[] A = {0,1,1,1,1}; // int[] A = {1,2,3,2,1}; int[] A = {0,0,0,0,0,0,1,0,0,0}; // int[] B = {1,0,1,0,1}; // int[] B = {3,2,1,4,7}; int[] B = {0,0,0,0,0,0,0,1,0,0}; System.out.println(findLength(A, B) ); } public static int findLength(int[] A, int[] B) { int ans = 0; int a = A.length; int b = B.length; for (int i=0; i<a; i++) { int len = Math.min(b, a-i); //确定同时开始的位置 int tmp = maxLength(A, B, i, 0, len); ans = Math.max(ans, tmp); } for (int i=0; i<b; i++) { int len = Math.min(a, b-i); //确定同时开始的位置 int tmp = maxLength(A, B, 0, i, len); ans = Math.max(ans, tmp); } return ans; } public static int maxLength(int[] A, int[] B, int addA, int addB, int len){ int ret = 0; int sum = 0; for (int i=0; i<len; i++) { if (A[i+addA] == B[i+addB]) { sum++; } else { sum = 0; } ret = Math.max(sum, ret); } return ret; } }