leetcode718 最长重复子数组

左手的ㄟ右手 2023-06-20 15:58 110阅读 0赞

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入:  
A: \[1,2,3,2,1\]  
B: \[3,2,1,4,7\]  
输出: 3  
解释:  
长度最长的公共子数组是 \[3, 2, 1\]。  
说明:

1 <= len(A), len(B) <= 1000  
0 <= A\[i\], B\[i\] < 100

思路：和最长公共子串一样（子数组是连续的）

class Solution {
        public int findLength(int[] A, int[] B) {
            int ans = 0;
            int[][] memo = new int[A.length + 1][B.length + 1];
            for (int i = A.length - 1; i >= 0; --i) {
                for (int j = B.length - 1; j >= 0; --j) {
                    if (A[i] == B[j]) {
                        memo[i][j] = memo[i+1][j+1] + 1;
                        if (ans < memo[i][j]) ans = memo[i][j];
                    }
                }
            }
            return ans;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191210205243467.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No.18】leetcode718. 最长重复子数组

【算法|动态规划No.18】leetcode718. 最长重复子数组

末蓝、/ 2024年04月27日 06:34/ 0 赞/ 65 阅读

相关 LeetCode-718. 最长重复子数组

目录题目思路动态规划遇到的坑动态规划(优化) 题目来源 [718. 最长重复子数组][718.]

r囧r小猫/ 2024年03月26日 22:01/ 0 赞/ 72 阅读

相关 LeetCode_动态规划_中等_718.最长重复子数组

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子

旧城等待，/ 2023年10月06日 23:20/ 0 赞/ 44 阅读

相关 leetcode718 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。示例 1: 输入: A: \[1,2,3,2,1\] B: \[3,2,1,4,7\]

左手的ㄟ右手/ 2023年06月20日 15:58/ 0 赞/ 111 阅读

相关 LeetCode 978. 最长湍流子数组

当 A 的子数组 A\[i\], A\[i+1\], …, A\[j\] 满足下列条件时，我们称其为湍流子数组：若 i <= k < j，当 k 为奇数时， A\[k\]

╰半橙微兮°/ 2022年10月29日 03:28/ 0 赞/ 126 阅读

相关 leetcode 718. Maximum Length of Repeated Subarray | 718. 最长重复子数组（动态规划）

题目 [https://leetcode.com/problems/maximum-length-of-repeated-subarray/][https_leetcod

短命女/ 2022年10月19日 04:15/ 0 赞/ 154 阅读

相关 NC41 最长无重复子数组

用到了双指针 i和j两个指针一开始都指向第0位，用一个HashMap来记录i指针走过的数字和所在位置。然后i开始往右移动，如果发现从j到i这一段里面有重复的数字，j就往

系统管理员/ 2022年09月16日 11:22/ 0 赞/ 146 阅读

相关 718 最长重复子数组（二分查找、字符串哈希）

1. 问题描述：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。示例：输入： A: \[1,2,3,2,1\] B: \[3,2,

桃扇骨/ 2022年09月09日 11:51/ 0 赞/ 148 阅读

相关最长重复子串

思路：使用后缀数组解决分析： 1、由于要求最长公共子序列，则需要找到字符串的所有子串，即通过产生字符串的后缀数组实现。 2、由于要求最长的重复子串，则需要对所有子串进行

刺骨的言语ヽ痛彻心扉/ 2022年06月17日 03:16/ 0 赞/ 211 阅读

相关 leetcode 718. 最长重复子数组

[https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/][https_leetcode-c

柔光的暖阳◎/ 2021年12月11日 10:19/ 0 赞/ 268 阅读