最长重复子数组

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

示例：

nums1 = [1,2,3,2,1]  
nums2 = [3,2,1,4,7]  
输出：3  
解释：最长重复子数组是 [3,2,1]，长度为 3。

解题思路

1. 暴力法的局限性
最直接的方法是枚举 nums1 的所有子数组，检查是否在 nums2 中出现。但这样时间复杂度会达到 O(n²·m)（设 n、m 为两数组长度），效率太低。

2. 动态规划的定义
我们可以用动态规划来优化。定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。

• 为什么是 i-1 和 j-1？这样可以将边界情况（i=0 或 j=0）视为空数组，方便初始化。

3. 状态转移方程
如果 nums1[i-1] == nums2[j-1]，说明当前元素可以延长公共子数组：
dp[i][j] = dp[i-1][j-1] + 1
如果不相等，则 dp[i][j] = 0（因为子数组必须连续，一旦不相等，当前结尾的公共长度就为 0）。

4. 初始化

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

5. 计算过程与示例
以示例为例：

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

构建 dp 表（行列各多一行用于边界）：

遍历过程中，当 nums1[2]=3 与 nums2[0]=3 相等时，dp[3][1] = dp[2][0] + 1 = 1；
当 nums1[3]=2 与 nums2[1]=2 相等时，dp[4][2] = dp[3][1] + 1 = 2；
当 nums1[4]=1 与 nums2[2]=1 相等时，dp[5][3] = dp[4][2] + 1 = 3。
最大值是 3。

6. 复杂度优化

• 时间复杂度：O(n·m)
• 空间复杂度：可优化到 O(min(n, m))，因为 dp 表每一行只依赖上一行。

7. 代码实现（简化版）

def findLength(nums1, nums2):
    n, m = len(nums1), len(nums2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    max_len = 0
    for i in range(1, n + 1):
        for j in range(1, m + 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])
    return max_len

8. 关键点总结

• 与“最长公共子序列”（不要求连续）的区别在于：一旦字符不匹配，当前状态直接归零。
• 动态规划表中最大值不一定出现在最后，需要全程记录最大值。