NC41 最长无重复子数组
2022/1/23 6:07:52
本文主要是介绍NC41 最长无重复子数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
描述
- 给定一个长度为n的数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。
- 子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
- 要求:空间复杂度 O(n),时间复杂度 O(nlogn)
方法一:滑动窗口法
- 算法思路
- 我们可以利用双指针模拟一个滑动窗口。初始化该窗口为(left, right]。所以left从-1开始。窗口不断往右扩大。因为我们要的是无重复子数组,因此,遇到有重复的数字,在窗口左侧进行缩小。
在每次滑动时,对窗口的大小进行比较,保留最大的长度。
import java.util.*; public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength (int[] arr) { // write code here if(arr.length < 2){ return arr.length; } HashMap<Integer, Integer> windows = new HashMap<>(); int res = 0; //用双指针来模拟一个滑动窗口 int left = -1; //窗口向右滑动 for(int right = 0; right < arr.length; right++){ //遇到重复数字 if(windows.containsKey(arr[right])){ //因为有可能遇到的重复数字的位置 比 left还要前 //所以不能把left置于该位置前一位, 而是比较哪个最大,目的还是为了缩小窗口 //确保窗口内全是不重复的数字 left = Math.max(left, windows.get(arr[right])); } //每次更新窗口大小 res = Math.max(res, right-left); //将数字位置更新到windows中 windows.put(arr[right], right); } return res; } }
算法复杂度
- 时间: O(n) n为数组的长度
- 空间:O(n) n为HashMap的长度。
这篇关于NC41 最长无重复子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享