一、问题描述

给定两个整数数组 A 和 B，返回两个数组中公共的、长度最长的子数组的长度。

二、方案一：动态规划

1、思路

设计思路：使用动态规划，dp[i][j] 表示以 A[i-1] 和 B[j-1] 结尾的公共子数组的长度。

• 初始化 dp 数组，所有位置为 0。
• 遍历数组 A 和 B，如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = 0。
• 最后 dp 数组中的最大值即为所求的最长重复子数组的长度。

2、代码实现

func findLength(A []int, B []int) int {
    if len(A) == 0 || len(B) == 0 {
        return 0
    }
    dp := make([][]int, len(A)+1)
    for i := range dp {
        dp[i] = make([]int, len(B)+1)
    }
    maxLen := 0
    for i := 1; i <= len(A); i++ {
        for j := 1; j <= len(B); j++ {
            if A[i-1] == B[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                maxLen = max(maxLen, dp[i][j])
            }
        }
    }
    return maxLen
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 分别是数组 A 和 B 的长度。
• 空间复杂度：O(mn)，需要额外的一个二维数组 dp 来存储每个位置的最长重复子数组的长度。

三、方案二：滑动窗口

1、思路

设计思路：由于重复子数组在两个数组中的位置可能不同，我们可以将一个数组固定，然后滑动另一个数组，找到最长的重复子数组。

• 对于数组 A 的每个位置 i，将数组 B 从头开始与 A[i:] 进行比较，找到最长的重复子数组。
• 对于数组 B 的每个位置 j，将数组 A 从头开始与 B[j:] 进行比较，找到最长的重复子数组。
• 最后，取上述所有情况中的最大值即为所求的最长重复子数组的长度。

2、代码实现

func findLength(A []int, B []int) int {
    maxLen := 0
    for i := 0; i < len(A); i++ {
        for j := 0; j < len(B); j++ {
            l := 0
            for i+l < len(A) && j+l < len(B) && A[i+l] == B[j+l] {
                l++
            }
            maxLen = max(maxLen, l)
        }
    }
    return maxLen
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 分别是数组 A 和 B 的长度。
• 空间复杂度：O(1)，只需要常数级别的额外空间。

四、总结

方案	时间复杂度	空间复杂度	说明
方案一	O(mn)	O(mn)	动态规划
方案二	O(mn)	O(1)	滑动窗口
方案一和方案二在时间复杂度上相同，但在空间复杂度上方案二更优。在实际应用中，可以根据具体需求选择合适的方案。