LeetCode最长重复子数组递归解法错误修复求助

你的递归逻辑核心错误在于：混淆了「以当前数组开头为起点的连续匹配长度」和「全局最长重复子数组长度」。当nums1[0] == nums2[0]时，你直接将1与后续递归的结果相加，但后续递归返回的可能是其他位置的非连续最长子数组长度，这就会错误地把分散的匹配长度累加，导致结果偏大。

修正后的朴素递归方案 #

我们可以拆分逻辑：用一个辅助递归函数专门计算以指定下标为起点的最长连续匹配子数组长度，再通过遍历所有可能的起始位置，找到全局最大值。

from typing import List

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        max_len = 0
        m, n = len(nums1), len(nums2)
        
        # 辅助函数：计算以nums1[i]和nums2[j]为起点的最长连续匹配长度
        def helper(i: int, j: int) -> int:
            if i >= m or j >= n:
                return 0
            if nums1[i] == nums2[j]:
                return 1 + helper(i + 1, j + 1)
            # 元素不相等时，连续匹配中断，返回0
            return 0
        
        # 遍历所有可能的起始位置，更新全局最长长度
        for i in range(m):
            for j in range(n):
                current_len = helper(i, j)
                if current_len > max_len:
                    max_len = current_len
        return max_len

逻辑说明 #

1. 辅助函数helper(i,j)：只负责计算从i和j开始的连续匹配长度，一旦遇到元素不相等就立即返回0，确保只累加连续的匹配项，不会混入非连续的结果。
2. 主函数遍历：通过枚举nums1和nums2的所有起始组合，调用辅助函数获取该起点的连续匹配长度，最终记录全局最大值。

这个方案可以正确处理你提到的测试用例：对于nums1=[0,1,1,1,1]和nums2=[1,0,1,0,1]，会找到nums1[0]与nums2[1]的连续匹配[0,1]（长度2），以及其他短匹配，最终返回正确的最大值2。

内容的提问来源于stack exchange，提问作者Victor Cui