Medium

题目描述

给两个整数数组 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
解释：长度最长的公共子数组是 [0,0,0,0,0]。

约束条件:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[j] <= 100

提示:

  • 使用动态规划。dp[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的最长公共子数组长度。
  • 答案是所有 dp[i][j] 中的最大值。

解题思路

这道题求解最长重复子数组，可以用多种方法解决。

方法一：动态规划（推荐） 核心思想是定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度。当 nums1[i-1] == nums2[j-1] 时，dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。这里关键在于子数组必须连续，所以不匹配时直接置0。

方法二：滑动窗口 通过枚举两个数组的相对位置，固定一个数组，让另一个数组滑动，在每个位置计算最长公共前缀。需要考虑 nums1 滑动和 nums2 滑动两种情况。

方法三：二分查找 + 哈希 二分查找答案长度，对于每个长度，用哈希表存储一个数组的所有该长度子数组，检查另一个数组是否有相同的子数组。

动态规划解法最直观且效率较高，时间复杂度 O(mn)，空间复杂度可优化至 O(min(m,n))。

代码实现

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        int maxLen = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = max(maxLen, dp[i][j]);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_len = 0
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    max_len = max(max_len, dp[i][j])
        
        return max_len

public class Solution {
    public int FindLength(int[] nums1, int[] nums2) {
        int m = nums1.Length, n = nums2.Length;
        int[,] dp = new int[m + 1, n + 1];
        int maxLen = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1] + 1;
                    maxLen = Math.Max(maxLen, dp[i, j]);
                }
            }
        }
        
        return maxLen;
    }
}

var findLength = function(nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    let maxLength = 0;
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型动态规划解法
时间复杂度O(m × n)
空间复杂度O(m × n)

注：m 和 n 分别为两个数组的长度。空间复杂度可以优化到 O(min(m, n))，使用滚动数组技巧。

相关题目