What is the primary approach to solving the Maximum Length of Repeated Subarray problem?

The problem is typically solved using state transition dynamic programming, where dp[i][j] represents the longest common prefix of subarrays starting at nums1[i:] and nums2[j:].

How does dynamic programming help solve the problem?

Dynamic programming is used to efficiently compute the longest common subarray by storing results of overlapping subproblems, reducing redundant calculations.

Can binary search optimize the Maximum Length of Repeated Subarray solution?

Yes, binary search can be used to narrow down the length of the longest common subarray, improving the time complexity of the solution.

What is the time complexity of the Maximum Length of Repeated Subarray problem?

The time complexity is O((M+N) * log(min(M, N))) due to the binary search and dynamic programming steps.

How can space complexity be optimized in this problem?

Space complexity can be optimized by using a rolling hash or by keeping only the current row of the dp table, thus reducing the memory usage.

#718

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。示例 1：输入： nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出： 3 解释：长度最长的公共子数组是 [3,2,1] 。示例 2：输入： nums1 …

数组二分查找动态规划滑动窗口滚动哈希

题目描述

给两个整数数组 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 <= 1000
0 <= nums1[i], nums2[i] <= 100

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示以 $nums1[i - 1]$ 和 $nums2[j - 1]$ 结尾的最长公共子数组的长度，那么我们可以得到状态转移方程：

f[i][j]= \begin{cases} 0, & nums1[i - 1] \neq nums2[j - 1] \\ f[i - 1][j - 1] + 1, & nums1[i - 1] = nums2[j - 1] \end{cases}

最终的答案即为所有 $f[i][j]$ 中的最大值。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是数组 $nums1$ 和 $nums2$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	O((M+N) * \log{(\min(M, N))})
空间	O(M)

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of state transition dynamic programming.
question_mark
The candidate should propose optimizations such as binary search or rolling hash.
question_mark
Pay attention to how well they can balance time and space complexity in their approach.

warning

常见陷阱

外企场景

error
Incorrectly handling indices while accessing elements in the dp table.
error
Over-complicating the solution when a simple dynamic programming approach suffices.
error
Failing to optimize for space when the problem constraints are large.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the arrays are very large (greater than 1000 elements)?
arrow_right_alt
Can this problem be solved in linear time?
arrow_right_alt
What if the arrays contain non-integer values or negative numbers?

help

常见问题

外企场景

继续练习

#1477 找两个和为目标值且不重叠的子数组 #713 乘积小于 K 的子数组 #689 三个无重叠子数组的最大和