Skip to main content

最长重复子数组

Tips

题目类型: Dynamic Programming

相关题目:

题目​

给两个整数数组 nums1 和 nh6bgytv5nums2, 返回两个数组中公共的, 长度最长的子数组的长度.

提示:
  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100
示例
输入: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出: 3
解释: 长度最长的公共子数组是 [3,2,1].
输入: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出: 5

题解​

dp 的定义是以下标 i - 1 为结尾的 nums1, 和以下标 j - 1 为结尾的 nums2, 最长重复子数组长度为 dp[i][j].

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
  const m = nums1.length
  const n = nums2.length
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))

  let max = 0
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      }

      max = Math.max(dp[i][j], max)
    }
  }

  return max
}

=-09