【LEETCODE】718.最长重复子数组-动态规划+滑动窗口

题目

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

思路

设数组A长度为n,B长度为m

  1. 动态规划
    设置动态规划数组dp[n+1][m+1],dp[n][m]=0。
    从A[n-1]和B[m-1]开始向前遍历比较,可以得出伪代码:

    if A[i]==B[j]:
    	dp[i][j]=dp[i+1][j+1]+1;
    else if A[i]!=B[j]:
    	dp[i][j]=0;
    
  2. 滑动窗口
    滑动窗口的示意图如下图所示:
    在这里插入图片描述

代码

1.动态规划

class Solution {
    public int findLength(int[] A, int[] B) {
        int output=0;
        for(int i=0;i<A.length;i++){
            for(int j=0;j<B.length;j++){
                int tmp=0;
                int l=i,r=j;
                while(l<A.length&&r<B.length&&A[l]==B[r]){
                    tmp++;
                    l++;
                    r++;
                }
                output=Math.max(output,tmp);
            }
        }
        return output;
    }
}

2.滑动窗口:

class Solution {
    public int findLength(int[] A, int[] B) {
        int n=A.length, m=B.length;
        int ans=0;
        for(int i=0;i<n;i++){
            int len=Math.min(m,n-i);
            int maxLen=maxLength(A,B,i,0,len);
            ans=Math.max(ans,maxLen);
        }
        for(int i=0;i<m;i++){
            int len=Math.min(n,m-i);
            int maxLen=maxLength(A,B,0,i,len);
            ans=Math.max(ans,maxLen);
        }
        return ans;
    }
    public int maxLength(int[] A, int[] B, int len1, int len2, int len){
        int ans=0,k=0;
        for(int i=0;i<len;i++){
            if(A[len1+i]==B[len2+i]){
                k++;
            }else{
                k=0;
            }
            ans=Math.max(ans,k);
        }
        return ans;
    }
}

复杂度分析:

  1. 动态规划:
    时间复杂度:O(mn)
    空间复杂度:O(m
    n)
  2. 滑动窗口:
    时间复杂度:O((m+n)*min(n,m))
    空间复杂度:O(1)

热门文章

暂无图片
编程学习 ·

java 中的反射技术

java代码 @SpringBootTest(classes = {ShujiegouApplication.class}) @RunWith(SpringJUnit4ClassRunner.class) public class FansheTest {@Testpublic void test1() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {SysColumn sysColumn …
暂无图片
编程学习 ·

Linux 文件系统解析(三)cache

Linux文件系统中使用了大量cache,用于提升IO性能,本篇来梳理一下这些与文件系统相关的cache,它们在内存中是如何组织管理的,它们是如何加速文件系统操作的。Dentry Cachedentry用于描述系统目录树中的一个节点,磁盘文件系统中通常没有相关结构,dentry只存在于内存之中,它…
暂无图片
编程学习 ·

动态规划(二)

大佬的第二个视频代码 视频链接 题目一: 题目描述: 在一个数组中(只包含正整数)找出一组不相邻的数,使得其和最大 解题思路: 关键思想: 每个数有选和不选两种选择。按前i个数的最优解来说,如果选这个数,则这个数的前一个数就不能选,因此此时的最优解就是前i-2个数的最…
暂无图片
编程学习 ·

低功耗蓝牙(BLE)和传感器的使用

一、低功耗蓝牙的使用Android中关于蓝牙的开发文档,可以参考Google提供的官方蓝牙文档:https://developer.android.google.cn/guide/topics/connectivity/bluetooth.html在Android开发中,应用可通过官方提供的蓝牙API执行以下操作:扫描其他蓝牙设备查询本地蓝牙适配器的配对…
暂无图片
中恒嘉业 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
cgfy ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…
暂无图片
coreui ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
未来博客 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
建站日记 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
mfbz ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…