js.最长重复子数组
链接：718. 最长重复子数组 - 力扣（LeetCode）
题目：
给两个整数数组
nums1和nums2，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出：5
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
题解思路：
方法：动态规划
暴力解法的过程中，我们发现最坏情况下对于任意 i 与 j ，A[i] 与 B[j] 比较了 min(i+1,j+1) 次。这也是导致了该暴力解法时间复杂度过高的根本原因。
不妨设 A 数组为 [1, 2, 3]，B 两数组为为 [1, 2, 4] ，那么在暴力解法中 A[2] 与 B[2] 被比较了三次。这三次比较分别是我们计算 A[0:] 与 B[0:] 最长公共前缀、 A[1:] 与 B[1:] 最长公共前缀以及 A[2:] 与 B[2:] 最长公共前缀时产生的。
我们希望优化这一过程，使得任意一对 A[i] 和 B[j] 都只被比较一次。这样我们自然而然想到利用这一次的比较结果。如果 A[i] == B[j]，那么我们知道 A[i:] 与 B[j:] 的最长公共前缀为 A[i + 1:] 与 B[j + 1:] 的最长公共前缀的长度加一，否则我们知道 A[i:] 与 B[j:] 的最长公共前缀为零。
这样我们就可以提出动态规划的解法：令 dp[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀，那么答案即为所有 dp[i][j] 中的最大值。如果 A[i] == B[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1，否则 dp[i][j] = 0。
这里借用了 Python 表示数组的方法，A[i:] 表示数组 A 中索引 i 到数组末尾的范围对应的子数组。
考虑到这里 dp[i][j] 的值从 dp[i + 1][j + 1] 转移得到，所以我们需要倒过来，首先计算 dp[len(A) - 1][len(B) - 1]，最后计算 dp[0][0]。
复杂度分析
时间复杂度： O(N×M)。
空间复杂度： O(N×M)。
N 表示数组 A 的长度，M 表示数组 B 的长度。
空间复杂度还可以再优化，利用滚动数组可以优化到 O(min(N,M))。
代码：
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findLength = function(nums1, nums2) {
let n = nums1.length , m = nums2.length
let num = 0
let dp = Array.from({ length: n+1 }, () => Array(m+1).fill(0));
// 得到全为0的二维数组dp
console.log(dp)
for(let i = n-1 ; i>=0 ; i-- ){
for(let j = m-1 ; j>=0 ; j-- ){
if(nums1[i]==nums2[j]){
dp[i][j] = 1+dp[i+1][j+1]
if(dp[i][j]>num) num = dp[i][j]
}
}
}
return num
};