最长重复子数组

718. 最长重复子数组

leetcode 链接

思路：

动态规划

1.确定 dp 数组含义：dp[i][j] 表示 nums1 子数组长度为 i，nums2 子数组长度为 j 的最长公共子数组的长度。

2.初始化 dp 数组，dp[i][0] = 0, dp[0][j] = 0。

3.确定遍历方向，从前往后遍历。

4.确定转移方程，当 nums1[i - 1] == nums2[j - 1] 时，最长公共子数组长度+1。不相等的话，不做处理，默认长度为 0。

5.记录 dp 的最大值, 最后返回该最大值

typescript 解法

function findLength(nums1: number[], nums2: number[]): number {
  const len1: number = nums1.length;
  const len2: number = nums2.length;

  const dp: number[][] = new Array(len1 + 1)
    .fill(0)
    .map(() => new Array(len2 + 1).fill(0));

  let max: number = 0;
  for (let i: number = 1; i <= len1; i++) {
    for (let j: number = 1; j <= len2; j++) {
      if (nums1[i - 1] == nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }
      max = Math.max(max, dp[i][j]);
    }
  }
  return max;
}

go 解法

func findLength(nums1 []int, nums2 []int) int {
    // 确定dp数组含义：dp[i][j]表示nums1子数组长度为i，nums2子数组长度为j的最长公共子数组的长度
    len1 := len(nums1)
    len2 := len(nums2)
    // 初始化dp数组，dp[i][0], dp[0][j]为0
    dp := make([][]int, len1 + 1)
    for i := 0; i <= len1; i ++ {
        dp[i] = make([]int, len2 + 1)
    }
    maxLength := 0
    // 确定遍历方向
    for i := 1; i <= len1; i ++ {
        for j := 1; j <= len2; j ++ {
            // 确地转换方程，当nums1[i - 1] == nums2[j - 1] 时，最长公共子数组长度+1
            // 不相等的话，不做处理，默认长度为0
            if nums1[i - 1] == nums2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            // 记录最大的最长公共子数组长度
            if dp[i][j] > maxLength {
                maxLength = dp[i][j]
            }
        }
    }
    // 返回最大的最长公共子数组长度
    return maxLength
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}