原题

718.最长重复子数组 2020年7月1日 每日一题

题解

方法一

暴力法。

/*暴力法 @v7fgg 执行用时：2265 ms, 在所有 Java 提交中击败了5.00%的用户 内存消耗：39.3 MB, 在所有 Java 提交中击败了100.00%的用户 2020年7月1日 8:03 */ class Solution { public int findLength(int[] A, int[] B) { int ans=0; for(int i=0;i<A.length;i++){ for(int j=0;j<B.length;j++){ if(A[i]==B[j]){ int ansT=0; int i1=i; int j1=j; while(i1<A.length&&j1<B.length&&A[i1]==B[j1]){ ansT++; i1++; j1++; } ans=Math.max(ans,ansT); } } } return ans; } }

方法二 动态规划

建立一个二维数组ans（行列数分别为A的长度加1和B的长度加1），其中ans[i][j]的含义为从之前的最早可能位置到A的i位置和B的j位置的最长的相同部分子序列。当移动到ans[i+1][j+1]的时候，有 ans[i+1][j+1]=A[i]==B[j]?ans[i][j]+1:0 通过遍历所有可能的i和j的组合从小到大，二层循环即可算出整个矩阵，取其中最大值。 本思路java代码示例：

/*dp @v7fgg 执行用时：73 ms, 在所有 Java 提交中击败了24.50%的用户 内存消耗：48.8 MB, 在所有 Java 提交中击败了100.00%的用户 2020年7月1日 8:34 */ class Solution { public int findLength(int[] A, int[] B) { int daan=0; int ans[][]=new int[A.length+1][B.length+1]; for(int i=1;i<=A.length;i++){ for(int j=1;j<=B.length;j++){ ans[i][j]=A[i-1]==B[j-1]?ans[i-1][j-1]+1:0; daan=Math.max(daan,ans[i][j]); } } return daan; } } /*sliding window @v7fgg 执行用时：55 ms, 在所有 Java 提交中击败了67.44%的用户 内存消耗：39.4 MB, 在所有 Java 提交中击败了100.00%的用户 2020年7月1日 10:15 */ class Solution { public int findLength(int[] A, int[] B) { int ans=0; for(int i=0;i<A.length;i++){ int ansT=0; for(int j=0;j<Math.min(B.length,A.length-i);j++){ if(A[i+j]==B[j]){ansT++;} else{ansT=0;} ans=Math.max(ans,ansT); } } for(int i=0;i<B.length;i++){ int ansT=0; for(int j=0;j<Math.min(A.length,B.length-i);j++){ if(B[i+j]==A[j]){ansT++;} else{ansT=0;} ans=Math.max(ans,ansT); } } return ans; } } /*sliding window simplifeid version @v7fgg 执行用时：61 ms, 在所有 Java 提交中击败了46.43%的用户 内存消耗：39.5 MB, 在所有 Java 提交中击败了100.00%的用户 2020年7月1日 12:16 */ class Solution { public int findLength(int[] A, int[] B) { int ans=0; int ansT=0; //i表示的滑动的数字范围 for(int i=0;i<=A.length+B.length-2;i++){ //以下j先以A的坐标为准 for(int j=Math.max(0,i+1-B.length);j<=Math.min(A.length-1,i);j++){ if(A[j]==B[B.length-1-i+j]){ansT++;} else{ansT=0;} ans=Math.max(ans,ansT); } ansT=0;//注意初始化 } return ans; } }