LeetCode 솔루션 분류
[9/20] 718. Maximum Length of Repeated Subarray
본문
Medium
4406109Add to ListShareGiven 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
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
Accepted
193,520
Submissions
376,706
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 3125 ms, faster than 86.65% of Python3 online submissions for Maximum Length of Repeated Subarray.
Memory Usage: 39.2 MB, less than 74.08% of Python3 online submissions for Maximum Length of Repeated Subarray.
Memory Usage: 39.2 MB, less than 74.08% of Python3 online submissions for Maximum Length of Repeated Subarray.
from collections import defaultdict
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
M, N = len(nums1), len(nums2)
dp = [ [0]*M for _ in range(N) ]
for i in range(M):
if nums1[i] == nums2[0]:
dp[0][i] = 1
for n in range(1, N):
for m in range(M):
if m == 0 and nums2[n] == nums1[m]: dp[n][0] = 1
elif nums2[n] == nums1[m]:
dp[n][m] = dp[n-1][m-1] + 1
return max(max(line) for line in dp)
