当前位置:网站首页>无重复字符的最长子串
无重复字符的最长子串
2022-08-09 12:01:00 【爱敲代码的Harrison】
题目
力扣链接:无重复字符的最长子串
题解
子串问题(或子序列问题)规律总结:必须以i位置结尾怎样怎样 或者 必须以i位置开始怎样怎样;把每个位置的答案求出了,最终答案就是所有答案中的最大值
子串跟子序列的区别:子串是必须连续的,子序列可以要求不连续
这个题就只有两个因素影响
- 上一个重复字符出现的位置在哪
- i-1位置结尾,往左推了多远
如何记录上一个重复字符出现的位置呢?可以用一个map,也可以自己用数组代替map。(建议能不用map的情况下,就不用map。虽然map的增删改查时间复杂度是O(1),数组寻址比map查找,在常数时间上更快一点!下文会举例子测试)
自己用数组代替map,数组的长度如何确定呢?如果给定的字符串只有大小写字母,那么数组长度可以改为128;如果给定的字符串只有小写字母,那么数组长度可以改为26
为什么要记录i-1位置结尾的情况下,往左推了多远呢?
因为此题的答案就是上述两个影响因素谁离我当前位置近,谁就是答案!
并且记录i-1位置结尾的情况下,往左推了多远,还有一个好处。我们不需要生成一个dp数组,每次都查找一遍;可以只用有限几个变量来滚动记录。因为要求的无重复字符的最长子串的长度就是上述两个影响因素谁离我近,最后下标相减,最后取最大值就是答案。
代码
public int lengthOfLongestSubstring(String s) {
if(s==null || s.equals("")){
return 0;
}
char[] str=s.toCharArray();
// 用数组代替map,常数时间会更快一点(map用来记录上一个重复字符出现的位置)
// 如果给定的字符串只有大小写字母,那么数组长度可以改为128
// 如果给定的字符串只有小写字母,那么数组长度可以改为26
int[] map=new int[256];
for(int i=0; i<256; i++){
map[i]=-1;
}
int len=0;
// pre记录i-1位置结尾的情况下,往左推,推不动的位置
int pre=-1;
int cur=0;
for(int i=0; i!=str.length; i++){
// i位置结尾的情况下,往左推,推不动的位置
// pre(i-1位置的信息) 更新为 i位置的信息
pre=Math.max(pre,map[str[i]]);
cur=i-pre;
len=Math.max(len,cur);
map[str[i]]=i;
}
return len;
}
时间复杂度分析
时间复杂度为O(N),额外空间复杂度为O(1)
虽然申请了一个长度为256的数组,但是是固定长度,跟N没有关系,所以这个操作的空间复杂度是O(1),此外还申请了几个变量,所以空间复杂度为O(1)
除了一个for循环,其余操作的时间复杂度都是O(1),所以时间复杂度是O(N)
map和数组查找的效率比较
上文说过,两者的时间复杂度都是O(1),但是数组寻址的常数时间比map更快一点。
可能用map查找的时候,JVM里面会有些缓存,所以区别不是
特别明显。
用毫秒看不出区别,用纳秒区别也不大,而且map竟然还快一点,可能是缓存的问题吧,本来还可以用微妙去试一下,到那时Java中没有直接获取微妙的方法,所以就没弄了,但是数组寻址确实是比map查找的常数时间更快一点,这一点毋庸置疑!
边栏推荐
- "Digital Economy Panorama White Paper" Special Analysis of Banking Industry Intelligent Marketing Application Released
- 软件测试——金融测试类面试题,看完直接去面试了
- 2022 Niu Ke Duo School (6) M. Z-Game on grid
- 香港服务器如何进行加密?
- 腾讯欲成育碧最大股东/ 米哈游招NLP内容生成研究员/ AI发现四千余物种濒临灭绝...今日更多新鲜事在此...
- 超越CLIP的多模态模型,只需不到1%的训练数据!南加大最新研究来了
- 张朝阳对话俞敏洪:一边是手推物理公式,一边是古诗信手拈来
- Information system project managers must memorize the core test sites (63) The main process of project portfolio management & DIPP analysis
- 00后写个暑假作业,被监控成这笔样
- 在北极都可以穿短袖了,温度飙升至32.5℃
猜你喜欢
曼城推出可检测情绪的智能围巾,把球迷给整迷惑了
【Untitled】
阿里云新增三大高性能计算解决方案,助力生命科学行业快速发展
[Microservice ~ Remote Call] Integrate RestTemplate, WebClient, Feign
两分钟录音就可秒变语言通!火山语音音色复刻技术如何修炼而成?
曲鸟全栈UI自动化教学(八):框架代码讲解和进一步优化
Too much volume... Tencent was asked on the side that the memory was full, what would happen?
The grep command Shell regular expressions, the three musketeers
ABAP 面试题:如何使用 ABAP 编程语言的 System CALL 接口,直接执行 ABAP 服务器所在操作系统的 shell 命令?
阻塞、非阻塞、多路复用、同步、异步、BIO、NIO、AIO 一锅端
随机推荐
The latest interview summary in 20022 brought by Ali senior engineer is too fragrant
微信支付开发流程
【无标题】
#物联网征文#小熊派设备开发实战
IDEA 关闭/开启引用提示Usages
1小时直播招募令:行业大咖干货分享,企业报名开启丨量子位·视点
脱光衣服待着就能减肥,当真有这好事?
阿里云新增三大高性能计算解决方案,助力生命科学行业快速发展
PM2 configuration file
ARP协议原理
又有大厂员工连续加班倒下/ 百度搜狗取消快照/ 马斯克生父不为他骄傲...今日更多新鲜事在此...
软件测试——金融测试类面试题,看完直接去面试了
C# 获取系统已安装的.NET版本
Scala Advanced (7): Collection Content Summary (Part 1)
MySQL principle and optimization of Group By optimization techniques
Nature:猪死亡1小时后,器官再次运转
Blocking, non-blocking, multiplexing, synchronous, asynchronous, BIO, NIO, AIO all in one pot
LeetCode #101. Symmetric Binary Tree
GET请求和POST请求区别
曼城推出可检测情绪的智能围巾,把球迷给整迷惑了