【每日一题】【集合增删】2022年1月13日-NC41 最长无重复子数组-220113/220122
2024-10-20 15:48:55
描述
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
数据范围：0\le arr.length \le 10^60≤arr.length≤106，0 < arr[i] \le 10^50<arr[i]≤105
要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
方法1：双层循环，加入set，有重复看下一个
import java.util.*;
public class Solution {
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
if(arr.length == 0) {
return 0;
}
int maxLen = 0;
for(int i = 0; i < arr.length; i++) {
Set<Integer> set = new HashSet<>();
set.add(arr[i]);
for(int j = i + 1; j < arr.length; j++) {
if(set.contains(arr[j])) {
break;
}
set.add(arr[j]);
}
maxLen = Math.max(maxLen, set.size());
}
return maxLen;
}
}
方法2：双指针优化（一层循环+一个指针），在循环内对指针进行变更
import java.util.*;
public class Solution {
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxLength (int[] arr) {
if(arr.length < 2) {
return arr.length;
}
int maxLen = 0;
Set<Integer> set = new HashSet<>();
int left = 0;
for(int i = 0; i < arr.length; i++) {
//循环移除直到不包含当前元素
while(set.contains(arr[i])) {
set.remove(arr[left++]);
}
set.add(arr[i]);
maxLen = Math.max(maxLen, i - left + 1);
}
return maxLen;
}
}
方法3：用一个集合保存无重复的元素--2022年1月22日更新，最简单
public int maxLength (int[] arr) {
int maxLen = 0;
List<Integer> list = new ArrayList<>();
for(int i = 0; i < arr.length; i++) {
while(list.contains(arr[i])) {
list.remove(0);
}
list.add(arr[i]);
maxLen = Math.max(maxLen, list.size());
}
return maxLen;
}
最新文章
- ASP.NET Core 中文文档 第四章 MVC（3.2）Razor 语法参考
- instanceof关键字
- SQL 2005 服务器更计算机名
- Technical news July-11
- php 如何造一个简短原始的数据库类用来增加工作效率
- hdu2457
- JSP 处理汉字信息
- Arduino智能小车实践学习报告
- ArcGIS Engine开发之旅07---文件地理数据库、个人地理数据库和 ArcSDE 地理数据库中的栅格存储加以比较 、打开栅格数据
- duilib corner属性的贴图技巧——让图片自动贴到控件的的某一边或者一角并自适应控件的大小
- Android之文字点击链接
- mssql字符串分割后的值，把表中不存在的插入表中
- BZOJ 2743: [HEOI2012]采花( 离线 + BIT )
- AppBoxFuture(二): Say goodbye to sql!
- CVTE C/C++开发工程师笔试题（一）
- 激活prompt
- yum install oracle-validated
- 三种方式控制GPIO
- FreeType的项目总是报error LNK2019: unresolved external symbol __imp错误
- LVS基本原理