[718] 最长重复子数组

给两个整数数组 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 <= 1000

0 <= nums1[i], nums2[i] <= 100

这也是一个求最长子序列的系列问题。注意最长子序列与最长子数组之间的区分，最长子数组要求连成的序列是连续的，而子序列是可以跳过子数组中某些元素的。

子序列问题，通常是设 dp[i] 为以 nums[i] 结尾的子序列的最值的求值结果。而既然是求子数组，那么通常 dp 数组就仅与 dp[i-1] 相关。若是求子序列，则可能需要遍历从0到i中的dp最大值来求解。

对于本题，由于有入参有两个，因此我们应分别对 nums1 与 nums2 进行遍历。判断字符相等时，则dp[i] 应在为加入当前字符前的最长值+1。之后的问题就直接套入公式即可。

function findLength(nums1: number[], nums2: number[]): number {
  let res = 0;
  // 设 dp[i][j] 为: 以nums1[i-1]结尾的子数组与 nums2[j-1] 结尾的子数组 的最长公共子数组
  const dp: number[][] = Array(nums1.length + 1)
    .fill(0)
    .map(x => Array(nums2.length + 1).fill(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;
        res = Math.max(res, dp[i][j]);
      }
    }
  }
  return res;
}