最长重复子数组

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

例如：

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

最长重复子数组是 [3,2,1]，长度为 3。

解题思路

1. 暴力法（理解问题）
最直接的方法是枚举 nums1 的所有子数组，检查是否在 nums2 中出现。

• 枚举 nums1 的起点 i 和 nums2 的起点 j，然后向后逐位比较，记录最长的匹配长度。
• 时间复杂度：O(n³) 或 O(n²·m)，效率太低，不可行。

2. 动态规划（DP）
定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。

• 如果 nums1[i-1] == nums2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
• 否则 dp[i][j] = 0（因为子数组必须连续，一旦不相等，当前长度归零）。
• 最终答案是所有 dp[i][j] 的最大值。

例子推导

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

DP 表（行列多一格，索引从 1 开始）：

最大值是 3（dp[5][3] 对应结尾为 nums1[4] 和 nums2[2] 的子数组 [3,2,1]）。

3. 滑动窗口优化
另一种思路：将两个数组对齐，错开比较。

• 固定 nums1，滑动 nums2，对每个对齐位置，计算最长连续匹配。
• 时间复杂度 O((n+m)·min(n,m))，空间 O(1)。

4. 二分+哈希（更优解法）
如果数组很长，可以用“二分答案” + 滚动哈希（Rabin-Karp）：

• 二分可能的最长长度 L。
• 检查是否存在长度为 L 的公共子数组：用哈希表存一个数组所有长度为 L 的子数组的哈希值，检查另一个数组是否有相同哈希值（需处理冲突）。
• 时间复杂度 O((n+m) log(min(n,m)))。

代码实现（动态规划）

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])
    return max_len