sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

最长重复子数组-718 #114

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释: 
长度最长的公共子数组是 [3, 2, 1]。

说明:

1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

定义 dp[i][j] 为数组 A 从 i 开始往后,且数组 B 从 j 开始往后的两个子数组所得到的最长子数组的长度。

如果 A[i] === B[i],那么 dp[i][j] 就等于 1 + dp[i + 1][j + 1],也就是两个数组的起点各往后移一位后的最长子数组长度,如果它们不相等,那么可以直接得到 dp[i][j] = 0。因为这两位为起点无法组成重复子数组。

注意这里我初始化的时候的循环条件都是 i <= al 这样超出一位的,把超出边界的一位初始化为 0,是为了 i = A.length - 1 这种情况下,也就是其中的一个数组的最后一位比较的时候,假设这时候 A[i] = B[j] 了,那么会去找 1 + dp[i + 1][j + 1] 此时超出了边界,但是这种情况下完全可以把 1 + 0 作为结果,也就是最长子数组长度为 1。这样就巧妙的处理了边界情况。

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
let findLength = function (A, B) {
  let dp = []
  let al = A.length
  let bl = B.length

  for (let i = 0; i <= al; i++) {
    dp[i] = []
    for (let j = 0; j <= bl; j++) {
      dp[i][j] = 0
    }
  }

  let max = 0
  for (let i = al - 1; i >= 0; i--) {
    for (let j = bl - 1; j >= 0; j--) {
      let a = A[i]
      let b = B[j]

      if (a === b) {
        dp[i][j] = dp[i + 1][j + 1] + 1
        max = Math.max(max, dp[i][j])
      } else {
        dp[i][j] = 0
      }
    }
  }
  return max
}