[718] 最长重复子数组

暴力解法

details

超时了

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
    let len1 = nums1.length,
        len2 = nums2.length;

    let ans = 0;

    let i = 0;
    while (i < len1) {
        // nums2 中找到 j
        let j = 0;
        while (j < len2) {
            if (nums2[j] === nums1[i]) {
                break;
            }
            j++;
        }

        let start = i;
        while (nums1[start] === nums2[j]) {
            ans = Math.max(ans, start - i + 1);
            j++;
            start++;
        }
        i++;
    }
    return ans;
};

动态规划

details

var findLength = function (nums1, nums2) {
    let len1 = nums1.length,
        len2 = nums2.length;

    // 创建一个 (len1+1) x (len2+1) 的二维数组，并初始化为 0
    let dp = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(0));
    let ans = 0;

    // 遍历 nums1 和 nums2，填充 dp 数组
    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                ans = Math.max(ans, dp[i][j]);
            }
        }
    }

    return ans;
};

// 示例用法
const nums1 = [1, 2, 3, 2, 1];
const nums2 = [3, 2, 1, 4, 7];
console.log(findLength(nums1, nums2)); // 输出 3 (最长公共子数组为 [3, 2, 1])