题目

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

示例：输入：A: [1,2,3,2,1] B: [3,2,1,4,7]

输出：3

解释：长度最长的公共子数组是 [3, 2, 1] 。

提示：1 <= len(A), len(B) <= 1000

0 <= A[i], B[i] < 100

解题思路分析

1、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func findLength(A []int, B []int) int {n, m := len(A), len(B)dp := make([][]int, n+1)for i := 0; i <= n; i++ {dp[i] = make([]int, m+1)}res := math.MinInt32for i := 1; i <= n; i++ {for j := 1; j <= m; j++ {if A[i-1] == B[j-1] {dp[i][j] = dp[i-1][j-1] + 1}if dp[i][j] > res {res = dp[i][j]}}}return res}

2、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func findLength(A []int, B []int) int {n, m := len(A), len(B)dp := make([]int, m+1)res := math.MinInt32for i := 1; i <= n; i++ {for j := m; j >= 1; j-- {if A[i-1] == B[j-1] {dp[j] = dp[j-1] + 1} else {dp[j] = 0 // 需要清0}if dp[j] > res {res = dp[j]}}}return res}

3、滑动窗口；时间复杂度O(n^2)，空间复杂度O(1)

func findLength(A []int, B []int) int {n, m := len(A), len(B)res := math.MinInt32for i := 0; i < n; i++ {length := min(n-i, m)maxLength := getMaxLength(A, B, i, 0, length)res = max(res, maxLength)}for i := 0; i < m; i++ {length := min(n, m-i)maxLength := getMaxLength(A, B, 0, i, length)res = max(res, maxLength)}return res}func getMaxLength(A, B []int, a, b int, length int) int {res := 0count := 0for i := 0; i < length; i++ {if A[a+i] == B[b+i] {count++} else {count = 0}res = max(res, count)}return res}func max(a, b int) int {if a > b {return a}return b}func min(a, b int) int {if a > b {return b}return a}

总结

Medium题目，子数组系列题目，滑动窗口和动态规划方法需要掌握