718.最长重复子数组

链接：718.最长重复子数组
难度：Medium
标签：数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希
简介：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

题解 1 - typescript

• 编辑时间：2020-07-01
• 执行用时：272ms
• 内存消耗：93.5MB
• 编程语言：typescript
• 解法介绍：dp[i][j]= A[i]===B[i] ? dp[i+1][j+1] + 1 : 0，倒序动态规划。

function findLength(A: number[], B: number[]): number {
  const aLen = A.length;
  const bLen = B.length;
  let max = 0;
  const dp: number[][] = new Array(aLen + 1).fill(0).map(_ => new Array(bLen + 1).fill(0));
  for (let i = aLen - 1; i >= 0; i--) {
    for (let j = bLen - 1; j >= 0; j--) {
      max = Math.max(max, (dp[i][j] = A[i] === B[j] ? dp[i + 1][j + 1] + 1 : 0));
    }
  }
  return max;
}