718. 最长重复子数组

1. 题目描述

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

示例：

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

提示：

• 1 <= len(A), len(B) <= 1000
• 0 <= A[i], B[i] < 100

  2. 解题思路

  对于这道题目，我们可以使用动态规划来解决。动态规划就是要保持上一个状态和下一个状态有关系，并且是连续的。这里的子数组就相当于子串，是连续的。

这里我们初始化一个dp数组保存当前的最大连续值，dp[i][j]表示数组A的前i个元素和数组B的前j个元素组成的最长公共子数组的长度。

在遍历数组时：

• 如果当前的两个元素的值相等，也就是A[i] === B[j]，则说明当前的元素可以构成公共子数组，所以让前一个元素的最长公共子数组的长度加一，此时的状态转移方程是：dp[i][j] = dp[i - 1][j - 1] + 1；
• 如果当前的两个元素的值不相等，所以此时的dp值保存为0（初始化为0）。

在遍历的过程中，不断更新最长公共子序列最大值。

复杂度分析：

• 时间复杂度：O(mn)，其中m和n分别是A和B两个数组的长度，这里我们需要两层遍历两个数组。

• 空间复杂度：O(mn)，其中m和n分别是A和B两个数组的长度，我们需要初始化一个dp二维数组来保存当前的最长公共子数组的长度。

  3. 代码实现

  /**
  * @param {number[]} A
  * @param {number[]} B
  * @return {number}
  */
  var findLength = function(A, B) {
    const m = A.length, n = B.length;
    let dp = new Array(m + 1)
    for (let i = 0; i <= m; i++) { 
        dp[i] = new Array(n + 1).fill(0);
    }
    let res = 0
    for(let i = 1; i <= m; i++){
        for(let j = 1; j <= n; j++){
            if(A[i - 1] === B[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            res = Math.max(dp[i][j], res)
        }
    }
    return res
  };

  4. 提交结果