Cocolib

Appearance

On this page

最长重复子数组 ​

TIP

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

思路 ​

  • dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）
  • 即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
718.最长重复子数组
js
var findLength = function(nums1, nums2) {
    let dp = Array(nums1.length +1).fill().map(() => Array(nums2.length + 1).fill(0))
    let res = 0
        for(let i=1;i<=nums1.length;i++){
            for(let j = 1;j<=nums2.length;j++){
                if(nums1[i-1]===nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1
                }
                if(res<dp[i][j])    res = dp[i][j]
            }
        }
    return res
}