最长公共子数组问题

题目描述
给定两个整数数组 nums1 和 nums2，返回两个数组中公共的、长度最长的连续子数组的长度。例如：
nums1 = [1,2,3,2,1]，nums2 = [3,2,1,4,7]，最长公共连续子数组是 [3,2,1]，长度为 3。

解题过程循序渐进讲解

第一步：理解问题核心

• “公共连续子数组”要求子数组在两个原数组中连续且顺序一致。
• 与“最长公共子序列（LCS）”不同，LCS 允许不连续，而本题要求连续。
• 目标：找出最长公共连续子数组的长度。

第二步：暴力解法（思考起点）

• 最直接的方法：枚举 nums1 的所有连续子数组，在 nums2 中查找匹配的连续子数组。
• 步骤：
  1. 遍历 nums1 的所有起点 i 和终点 j（i ≤ j），得到子数组 nums1[i:j+1]。
  2. 在 nums2 中遍历所有起点 p，检查 nums2[p:p+len] 是否与 nums1[i:j+1] 完全相同（len = j-i+1）。
• 时间复杂度：O(m² * n * min(m,n))，其中 m、n 为数组长度。效率极低。

第三步：动态规划思路引入

• 观察到：如果 nums1[i] == nums2[j]，且我们知道以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组长度，就能递推。
• 定义状态：
  dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共连续子数组的长度。
  • 使用 i-1、j-1 是为了方便处理边界（避免 i=0 或 j=0 时的额外判断）。
• 状态转移方程：
  如果 nums1[i-1] == nums2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
  否则 dp[i][j] = 0（因为连续要求，一旦不等，当前结尾的公共长度就为 0）。
• 最终答案：所有 dp[i][j] 中的最大值。

第四步：动态规划实现细节

1. 初始化二维数组 dp，大小为 (m+1) × (n+1)，初始值全为 0。
2. 两层循环遍历 i 从 1 到 m，j 从 1 到 n：
   • 比较 nums1[i-1] 和 nums2[j-1]。
   • 若相等，dp[i][j] = dp[i-1][j-1] + 1。
   • 同时更新全局最大值 max_len。
3. 返回 max_len。

示例推导（用题目例子）
nums1 = [1,2,3,2,1]
nums2 = [3,2,1,4,7]
dp 表（只写部分关键值）：

• i=3（nums1[2]=3）, j=1（nums2[0]=3）：相等 → dp[3][1] = dp[2][0]+1 = 1
• i=4（2）, j=2（2）：相等 → dp[4][2] = dp[3][1]+1 = 2
• i=5（1）, j=3（1）：相等 → dp[5][3] = dp[4][2]+1 = 3
  最大值为 3。

第五步：优化空间复杂度

• 观察状态转移：dp[i][j] 只依赖于 dp[i-1][j-1]，即左上角的值。
• 可以优化为一维数组 dp，长度 n+1。
• 遍历顺序：i 从 1 到 m，j 从 n 到 1（倒序，避免覆盖上一行需要的 dp[j-1]）。
• 状态转移：
  如果 nums1[i-1] == nums2[j-1]，则 dp[j] = dp[j-1] + 1；否则 dp[j] = 0。
  注意：dp[j-1] 是上一轮（i-1）时 j-1 的值，即原来的 dp[i-1][j-1]。
• 空间复杂度从 O(m×n) 降为 O(n)。

第六步：代码实现（Python）

def findLength(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [0] * (n + 1)
    max_len = 0
    for i in range(1, m + 1):
        # 倒序更新，防止覆盖
        for j in range(n, 0, -1):
            if nums1[i-1] == nums2[j-1]:
                dp[j] = dp[j-1] + 1
                max_len = max(max_len, dp[j])
            else:
                dp[j] = 0
    return max_len

第七步：复杂度分析

• 时间复杂度：O(m × n)，两层循环。
• 空间复杂度：O(n)，使用一维 dp 数组。

第八步：扩展思考

• 如果要求输出最长公共子数组本身（而不仅是长度），可以在更新 max_len 时记录对应的索引位置。
• 另一种解法：滑动窗口法（对齐两个数组的起始位置，模拟错位比较），时间复杂度相同，但常数可能更优。
• 相关题目对比：
  • 最长公共子序列（LCS）：允许不连续，dp 状态转移为 dp[i][j] = max(dp[i-1][j], dp[i][j-1])（当字符不等时）。
  • 最长重复子数组：实际是本题的特例（两个输入数组相同）。

总结
最长公共子数组问题是动态规划的经典应用，通过定义“以当前位置结尾”的状态，将连续匹配的信息传递下去。掌握一维空间优化技巧，可以提升实际面试中的代码效率。