Description
Given two integer arrays nums1
and nums2
, return the maximum length of a subarray that appears in both arrays.
Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].
Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].
Constraints:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
Solutions
Solution 1
| class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
f = [[0] * (n + 1) for _ in range(m + 1)]
ans = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
f[i][j] = f[i - 1][j - 1] + 1
ans = max(ans, f[i][j])
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[][] f = new int[m + 1][n + 1];
int ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
ans = Math.max(ans, f[i][j]);
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<vector<int>> f(m + 1, vector<int>(n + 1));
int ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
ans = max(ans, f[i][j]);
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | func findLength(nums1 []int, nums2 []int) (ans int) {
m, n := len(nums1), len(nums2)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if nums1[i-1] == nums2[j-1] {
f[i][j] = f[i-1][j-1] + 1
if ans < f[i][j] {
ans = f[i][j]
}
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function findLength(nums1: number[], nums2: number[]): number {
const m = nums1.length;
const n = nums2.length;
const f = Array.from({ length: m + 1 }, _ => new Array(n + 1).fill(0));
let ans = 0;
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
ans = Math.max(ans, f[i][j]);
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | /**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findLength = function (nums1, nums2) {
const m = nums1.length;
const n = nums2.length;
const f = Array.from({ length: m + 1 }, _ => new Array(n + 1).fill(0));
let ans = 0;
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
ans = Math.max(ans, f[i][j]);
}
}
}
return ans;
};
|