leetcode 718.最长重复子数组

原题

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