LeetCode 718. 最长重复子数组

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 718. 最长重复子数组

思路分析

解法一：动态规划（推荐）

核心思路：

设 dp[j] 表示以 nums1[i-1] 与 nums2[j-1] 结尾的最长公共子数组长度。

当 nums1[i-1] == nums2[j-1] 时，dp[j] = dp[j-1] + 1，否则为 0。

为避免覆盖，j 从后往前更新。

复杂度分析：

时间复杂度：O(n*m)，其中 n、m 分别为两数组长度。

空间复杂度：O(m)，使用一维滚动数组。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[] dp = new int[m + 1];
        int ans = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    ans = Math.max(ans, dp[j]);
                } else {
                    dp[j] = 0;
                }
            }
        }

        return ans;
    }
}

func findLength(nums1 []int, nums2 []int) int {
	m := len(nums2)
	dp := make([]int, m+1)
	ans := 0

	for i := 1; i <= len(nums1); i++ {
		for j := m; j >= 1; j-- {
			if nums1[i-1] == nums2[j-1] {
				dp[j] = dp[j-1] + 1
				if dp[j] > ans {
					ans = dp[j]
				}
			} else {
				dp[j] = 0
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
1143. 最长公共子序列	中等	动态规划
718. 最长重复子数组	中等	动态规划
1035. 不相交的线	中等	动态规划
300. 最长递增子序列	中等	动态规划
647. 回文子串	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/15544319