前往此题

滑动窗口

将两个数组移至对齐，如数组[1,2,3,2,1]和 [3,2,1,4,7],其中3,2,1为它们的最长公共子数组，为了产生对齐需要对两个数组进行偏差遍历来取到重复子数组。

算法过程：

• 从nums1的第0个元素开始遍历对nums2进行匹配，如遇到相同元素记作ret += 1
• 接着从nums1的第二个元素开始遍历对nums2进行匹配，如此往复直到找到最大的ret
• 为了确保严谨nums2也要执行此遍历

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        def maxLength(addA, addB, length):
            ret = k = 0
            for i in range(length):
                if nums1[addA + i] == nums2[addB + i]:
                    k += 1
                    ret = max(ret, k)
                else:
                    k = 0
            return ret
        
        n, m = len(nums1), len(nums2)
        ret = 0
        for i in range(n):
            length = min(m, n - i)
            ret = max(ret, maxLength(i, 0, length))
        for i in range(m):
            length = min(n, m - i)
            ret = max(ret, maxLength(0, i, length))
        return ret