algorithms►leetcode

005-最长重复子数组（滑动窗口）

最长重复子数组超详细解析（从零开始）

最长重复子数组问题是指：给定两个整数数组，找出它们中共有的最长子数组的长度。这里的子数组要求是连续的。

1.问题描述

给定两个整数数组 nums1 和 nums2，返回两个数组中公共的、长度最长的子数组的长度。示例：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]。

2. 动态规划解法详解

2.1 为什么用动态规划？

因为这个问题具有：

  • 重叠子问题：大问题的解依赖小问题的解
  • 最优子结构：整体最优解包含子问题的最优解

2.2 DP表格的含义

我们创建一个表格，dp[i][j]表示：

  • 以nums1[i-1]和nums2[j-1]结尾的公共子数组的长度

注意：i和j从1开始，0行0列表示空数组

2.3 具体步骤（以[1,2,3,2,1]和[3,2,1,4,7]为例）

第一步：初始化表格

创建(m+1)×(n+1)的表格，全部填0：

   0 3 2 1 4 7
0 [0,0,0,0,0,0]
1 [0,0,0,0,0,0] 
2 [0,0,0,0,0,0]
3 [0,0,0,0,0,0]
2 [0,0,0,0,0,0]
1 [0,0,0,0,0,0]

第二步：填充表格

规则：

  • 如果nums1[i-1] == nums2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
  • 否则dp[i][j] = 0

填充过程：

  1. nums1[0]=1 vs nums2[0]=3 → 不相等 → dp[1][1]=0
  2. nums1[0]=1 vs nums2[2]=1 → 相等 → dp[1][3] = dp[0][2]+1 = 1
  3. nums1[1]=2 vs nums2[1]=2 → 相等 → dp[2][2] = dp[1][1]+1 = 1
  4. nums1[2]=3 vs nums2[0]=3 → 相等 → dp[3][1] = dp[2][0]+1 = 1
  5. 继续这样填完整张表…

最终表格：

   0 3 2 1 4 7
0 [0,0,0,0,0,0]
1 [0,0,0,1,0,0] 
2 [0,0,1,0,0,0]
3 [0,1,0,0,0,0]
2 [0,0,2,0,0,0]
1 [0,0,0,3,0,0]

第三步：找最大值

表格中最大的数字是3，所以最长重复子数组长度是3。

2.4 为什么这样计算？

因为：

  • 当两个数字相等时，它们可以扩展前面的公共子数组
  • dp[i][j] = dp[i-1][j-1] + 1表示”前面的能连多长，我就比它多1”
  • 表格中的数字就像”以这两个位置结尾的公共串长度”

3. 代码逐行解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function findLength(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    // 创建(m+1)×(n+1)的表格，初始化为0
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    let maxLen = 0; // 记录最大值
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                // 数字相等，长度+1
                dp[i][j] = dp[i - 1][j - 1] + 1;
                // 更新最大值
                maxLen = Math.max(maxLen, dp[i][j]);
            }
            // 不相等时保持0，不用写
        }
    }
    
    return maxLen;
}

4. 实际例子演练

让我们用nums1 = [0,1,1,1,1]和nums2 = [1,0,1,0,1]来演练：

4.1 初始化表格

创建6×6的全0表格

4.2 关键填充步骤：

  1. nums1[0]=0 vs nums2[1]=0 → dp[1][2] = dp[0][1]+1 = 1
  2. nums1[2]=1 vs nums2[0]=1 → dp[3][1] = dp[2][0]+1 = 1
  3. nums1[2]=1 vs nums2[2]=1 → dp[3][3] = dp[2][2]+1 = 1
  4. nums1[3]=1 vs nums2[4]=1 → dp[4][5] = dp[3][4]+1 = 2
  5. nums1[4]=1 vs nums2[4]=1 → dp[5][5] = dp[4][4]+1 = 3

4.3 最终表格（部分）：

dp[4][5] = 2  // 对应[1,1]和[1,1]
dp[5][5] = 3  // 对应[1,1,1]和[1,0,1]中的后两个1

最大值为2（虽然dp[5][5]=3，但实际公共子数组是”1,1”）

5. 常见误区

  1. 子数组 vs 子序列：

    • 子数组必须连续
    • 子序列可以不连续

  2. 初始化为1：

    • 很多人会想”至少长度是1”，但其实应该从0开始
    • 因为dp[i][j]表示的是”以这两个元素结尾”的长度

  3. 边界条件：

    • 一定要有i=0和j=0的行列
    • 它们代表空数组的情况

6. 优化思路

实际可以只用一维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function findLength(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    let dp = Array(n + 1).fill(0);
    let maxLen = 0;
    
    for (let i = 1; i <= m; i++) {
        const current = Array(n + 1).fill(0);
        for (let j = 1; j <= n; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                current[j] = dp[j - 1] + 1;
                maxLen = Math.max(maxLen, current[j]);
            }
        }
        dp = current;
    }
    
    return maxLen;
}

这样空间复杂度从O(mn)降到O(n)。

7. 总结关键点

  1. dp[i][j]表示的是以nums1[i-1]和nums2[j-1]结尾的公共子数组长度
  2. 只有当两个数字相等时才需要更新值
  3. 最大值可能在表格任意位置，需要全程记录
  4. 初始化的(m+1)×(n+1)表格中，第0行和第0列都是0

通过这样的分解，你应该能完全理解这个问题了。动态规划的关键就是找到这个状态转移方程，然后小心地填充表格。