最长重复子数组

题目描述
给定两个整数数组 nums1 和 nums2，返回两个数组中公共的、长度最长的子数组的长度。这里的“子数组”要求连续。
示例：

nums1 = [1,2,3,2,1]  
nums2 = [3,2,1,4,7]  
最长公共子数组是 [3,2,1]，长度为 3。

解题思路
本题要求找最长公共子数组（连续），常用方法是动态规划（DP）或滑动窗口。下面以 DP 为主讲解。

步骤 1：定义 DP 状态

定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。

• 使用 i-1 和 j-1 是为了避免边界判断，让 i=0 或 j=0 表示空子数组。

步骤 2：状态转移方程

如果 nums1[i-1] == nums2[j-1]，那么：

dp[i][j] = dp[i-1][j-1] + 1

否则：

dp[i][j] = 0

因为子数组必须连续，一旦字符不相等，以当前位置结尾的公共子数组长度就是 0。

步骤 3：初始化

dp[0][j] = 0（nums1 取空数组）
dp[i][0] = 0（nums2 取空数组）

步骤 4：计算过程与示例

以示例数据演示：

nums1 = [1,2,3,2,1]  
nums2 = [3,2,1,4,7]  

构建 DP 表（行列多出一行一列用于初始化）：

• 例如 dp[6][3] 对应 nums1[5]=1 和 nums2[2]=1 相等，所以 dp[6][3] = dp[5][2] + 1 = 2+1=3。
• 遍历过程中记录最大值 max_len = 3。

步骤 5：复杂度分析

• 时间复杂度：O(m×n)，m 和 n 为两数组长度。
• 空间复杂度：可优化到 O(min(m,n))，只保留上一行 DP 值。

步骤 6：代码实现（简化版）

def findLength(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                max_len = max(max_len, dp[i][j])
            else:
                dp[i][j] = 0
    return max_len

总结
通过 DP 表记录以每个位置结尾的公共子数组长度，利用连续性质在不相同时置 0，最终得到最大值。