718. 最长重复子数组

title: 中等 – 718. 最长重复子数组
date: 2020-07-01 19:32:30
tags:

• 数据结构与算法
• leetcode
  categories:
• 每天一道leetcode

• 中等
  toc: true

  求两个一维数组的最长重复子数组，具体见正文内链接。

题目链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

知识点：

• 动态规划（Dynamic Programming，DP）
• 滑动窗口
• 二分查找
• hash
• Rabin-Karp 算法（计算hash）

说明：本题自己的思路不足以解决此问题，以下是对官方题解的理解和总结

解法一：暴力枚举

代码

/*
* @author: mychangee
* @date: 2020-07-01 14:23
*/
import java.lang.Math;

class Solution {

    /*
    * @param: int[]
    * @param: int[]
    * @return: int
    */
    public int findLength(int[] A, int[] B) {
        int ans = 0, k;

        for(int i = 0; i < A.length - 1; i++){
            for(int j = 0; j < B.length -1; j++){
                k = 0;
                while(A[i + k] == B[j + k])
                    k++;
                ans = Math.max(ans, k);
            }
        }
    //---------
        int ans = 0;
        int len = Math.min(A.length,B.length);
        int k = 0;
        for(int i = 0; i < len - 1; i++){
            if(A[i] == B[i])
                k = k + 1;
            else
                k = 0;
            ans = Math.max(ans, k);
        }
        return ans;
    }
}

思路

1. 使用嵌套循环分别访问两个数组的值
2. 在循环中使用while循环判断两个数组分别从当前位置开始的元素有几个相同，并判断相同的元素的数量，记位k
3. 每次比较结束后，使用变量ans记录ans和k中的最大值，即最多连续了几次；循环结束后，最终的ans变量的值就是最大连续子数组的长度

问题&解决方法

1. 问题1：将多个元素重复进行比较

   比如A = [5, 1, 2, 4]和B = [1, 2, 1, 4]两个数组，当i = 1，j = 0时（A的第二三个元素和B的第一二个元素比较），和i = 2， j = 1时（A的第三个元素和B的第二个元素比较），两种情况下，程序将A的第3个元素和B的第二个元素比较了两次

   解决方法：使用动态规划，记录每次比较的结果，避免重复比较

解法二：动态规划（优化时间复杂度）

代码

/*
* @author: LeetCode-Solution
*/
class Solution {
    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;
    }
}

思路

1. 使用长宽分别为数组A的长度和B的长度的二维数组存储两个数组对应位置的比较结果
2. 两个数组倒序比较，如果A与B元素相等，dp[i][j] = dp[i+1][j+1] + 1，否则dp[i][j] = 0；
3. 每次比较后，将ans和dp中的最大值存储到变量ans中，比较结束后，最终的ans值就是最终结果

问题&解决方法

1. 问题：程序中使用了辅助二维数组dp，增加了空间复杂度；

   解决方法：使用滑动窗口，取消dp数组

解法三：滑动窗口（进一步优化空间复杂度）

代码

/*
* @author: mychangee
* @date: 2020-07-01 14:23
*/
import java.lang.Math;

class Solution {

    /*
    * @param: int[]
    * @param: int[]
    * @return: int
    */
    public int findLength(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;
    }

    /*
    * @param: int[]
    * @param: int[]
    * @param: int
    * @param: int
    * @param: int
    * @return: int
    */
    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);
        }

    return ret;
    }
}

思路

1. 用到两种算法：动态规划（DP）和滑动窗口
2. 在基础解法，即暴力枚举的基础上，为了优化时间复杂度，使用了DP，为了进一步优化空间复杂度，使用了滑动窗口
3. 滑动窗口解释：
   1. 首先，B数组不动，将A数组左移
   2. 其次，A数组不懂，将B数组左移
   3. 两种移动方法，覆盖了两个数组对齐的所有可能，在每次滑动后，比较两个数组中对应的值，取k的最大值
   4. 在两种滑动方法的所有移动结果中，取最大的k值，即为最后的结果

问题&解决方法

1. 时间复杂度还可以进一步优化
   1. 使用二分查找法进行比较，二分查找本身是较快速的查找方法
   2. 使用hash来在二分查找分中进行比较，进一步加快比较速度，从而提高整体速度

解法四：二分查找+Hash（未填充）

日拱一卒，功不唐捐！