718、求两个数组中公共的、长度最长的子数组的长度

方法一：动态规划

 时间复杂度： O(N×M)。  空间复杂度： O(N×M)。  N 表示数组 A 的长度，M 表示数组 B 的长度。  空间复杂度还可以再优化，利用滚动数组可以优化到 O(min(N,M))。 代码实现：   数组A=[1,2,3,2,1]   数组B=[3,2,1,4,7]

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; }

代码执行流程分析及结果图： 最长的公共子数组就是上面红色所对应的[3,2,1]，长度是3。

方法二：滑动窗口

 时间复杂度：O((N+M)×min(N,M))。  空间复杂度：O(1)。  N 表示数组 A 的长度，M 表示数组 B 的长度。 代码实现：

public int findLength2(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); System.out.println(i+" "+ret); } return ret; }

代码执行流程分析及结果图：

最长的公共子数组就是上面红色所对应的[3,2,1]，长度是3。是在第一个for循环是i=3,len=2,的时候取得。

总结：

  其实两种方法的本质是一样的，滑动窗口法相当于用时间复杂度换得动态规划法的空间复杂度。看做滑动窗口法容易理解一些，如两个数组A、B，都相当于移动数组B，使得B数组的起始位置对应第A数组的不同位置，然后求得两个数组公共部分的最长相同子数组的长度，依次类推，求出每个起始位置对应的相同子数组长度，然后取最大值即可。