Java刷题笔记1：最长重复子数组

Java刷题笔记1：最长重复子数组

题目描述:示例：暴力法：动态规划：

题目描述:

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入:A: [1,2,3,2,1] B: [3,2,1,4,7] 输出:3 解释:长度最长的公共子数组是 [3, 2, 1]。

点击跳转题目链接

在LeetCode中这题属于中等难度题，一般来说中等难度题无法使用暴力法通过。但是本人头铁，就是想试一试，反正暴力法写起来相对来说是最简单的。当然，最主要的原因是通过暴力法我们能够清楚的感受到算法存在哪些不足、哪些地方可以改进。进而写出令自己满意的代码。

暴力法：

每次我们从A组中选取一个子数组，然后去B组中找到一个与它相同的。我们可以先选取长度为Math.max（A.length,B.length）的子数组，然后慢慢减少长度，直到长度为0.

public static int findLength(int[] A, int[] B) { //取A中的一个子数组，然后去B中寻找相同的子数组 int windowSize = Math.min(A.length, B.length); while (windowSize > 0) { int start = 0;//用来记录目前A中子数组的开始下标 while (windowSize + start <= A.length) { for (int i = 0; i <= B.length - windowSize; i++) { //在B中匹配一个相同的数组 boolean flag = true;//用以判断是否完成匹配 for (int j = i; j < i + windowSize; j++) { if (A[start + j - i] != B[j]) {//当子数组中存在不同数字时结束循环 flag = false; break; } } if (flag == true) {//匹配成功 return windowSize; } } start++;//若在B数组中没有找到当前A中子串，则向右移动 } windowSize--;//减少窗口大小，即减少子串长度 } return 0; }

上面的代码一看时间复杂度就很高，循环写了好几层。虽然结果没问题，但是显然不能让人满意。问题出在哪里呢？我们在用A中取出子数组与B数组匹配时进行了许多重复的判断。用题目给到的例子来解释。我们一开始取出A中的{1,2,3,2,1},然后与B匹配，判断A[0]与B[0]是否相等。结束循环，缩小窗口，取出A中的{1,2,3,2},继续与B匹配，判断A[0]与B[0]是否相等…有此可见，我们对于已经判断过的元素并没有好好利用起来。刷题经验丰富的同学可能看出来了，这完全可以用动态规划的思想来减少重复判断啊。

动态规划：

我们使用dp[i][j]来保存A[ 0 : i ] (A[0]到A[i]) 与 B[ 0 : j ]的最长公共前缀长度。dp[i][j]可由dp[i-1][j-1]转移而来。当A[ i ]!=B[ j ]时dp[ i ][ j ] = 0.若A[ i ]==B[ j ] 那么dp[ i ][ j ]=dp[ i -1 ][ j - 1 ]+ 1.由于我们只需要最大值，所以每次计算完dp[i][j]后都将maxLength与它比较一下，然后取较大者。

public static int findLength2(int[] A, int[] B) { //dp[i][j] 表示A[0:i]与B[0:j]的最长公共前缀 //当A[i]=B[j]时，dp[i][j]=dp[i-1][j-1]+1;否则为0； int ans = 0; int[][] dp = new int[A.length + 1][B.length + 1]; for (int i = 0; i < A.length; i++) for (int j = 0; j < B.length; j++) { dp[i + 1][j + 1] = A[i] == B[j] ? dp[i][j] + 1 : 0; ans = Math.max(dp[i + 1][j + 1], ans); } return ans; }

在上述的代码中，我们申请了 (A.length+1)(B.length+1)的空间。若不这样处理那么在处理dp[0][0]时就会出现数组越界的问题，这样处理以后我们可以直接从dp[1][1]开始计算，而不用担心数组越界的问题。 这个时候，我们就完美的解决了重复计算的问题。当然，这题仍然有改进的空间。若是有时间的话就更新一下。