题目描述
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
- 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
- 输出：3
- 解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
- 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
- 输出：5
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
解法一：暴力解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
func max(nums ...int) int {
res := nums[0]
for _, val := range nums {
if val > res {
res = val
}
}
return res
}
func findLength(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
cur := 0
for i+cur < m && j+cur < n && nums1[i+cur] == nums2[j+cur] {
cur++
}
ans = max(cur, ans)
}
}
return ans
}
|
解法二：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
func max(nums ...int) int {
res := nums[0]
for _, val := range nums {
if val > res {
res = val
}
}
return res
}
func findLength(nums1 []int, nums2 []int) int {
h, w := len(nums1), len(nums2)
dp := make([][]int, h+1)
for i := 0; i < h+1; i++ {
dp[i] = make([]int, w+1)
}
ans := 0
for i := h - 1; i >= 0; i-- {
for j := w - 1; j >= 0; j-- {
if nums1[i] == nums2[j] {
dp[i][j] = dp[i+1][j+1] + 1
} else {
dp[i][j] = 0
}
ans = max(ans, dp[i][j])
}
}
return ans
}
|
