엔지니어 게시판
LeetCode 솔루션 분류

[9/20] 718. Maximum Length of Repeated Subarray

컨텐츠 정보

본문

Medium
4406109Add to ListShare

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

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= 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.
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)
                
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 159 명
  • 오늘 방문자 2,425 명
  • 어제 방문자 6,462 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,050 명
알림 0