当前位置:网站首页>【刷题记录】3. 无重复字符的最长子串
【刷题记录】3. 无重复字符的最长子串
2022-07-07 21:49:00 【InfoQ】
一、题目描述
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
二、思路分析
- 定义一个记录起始的start 和一个记录末尾的 end 如例1 中的abc这个窗口(start=0,end=3)是满足题目要求的
- 当窗口继续扩大为abca时,就会不满足,我们只有让有移动start(start+n),知道没有重复的为止,例子移动后变为bca。
- 在窗口扫描的过程中一直记录窗口的长度(end-start),更新为移动过程中最大的。既为我们需要的最终答案
- 同时为了更快判断的获取窗口内是否存在重复的值和值的位置 我们可以用一个哈希表来记录值和位置。
三、代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character,Integer> map = new HashMap<>();
//记录结果 即窗口的最大长度
int resultMax = 0;
//窗口最开始的左边界和右边界
int start = 0;
int end = 0;
for ( end = 0; end < s.length() ; end ++) {
if (map.containsKey(s.charAt(end))){
//窗口内存在重复的值时 移动窗口的左边界start
start = Math.max(start,map.get(s.charAt(end)) + 1);
}
map.put(s.charAt(end),end);
resultMax = Math.max(resultMax,end - start + 1 );
}
return resultMax;
}
}
总结
边栏推荐
- Qt Graphicsview图形视图使用总结附流程图开发案例雏形
- 微生物健康网,如何恢复微生物群落
- Robot autonomous exploration series papers environment code
- Unity FAQ (I) lack of references
- How to choose the appropriate automated testing tools?
- C development - interprocess communication - named pipeline
- Nx10.0 installation tutorial
- Debezium系列之:源码阅读之BinlogReader
- 0-5vac to 4-20mA AC current isolated transmitter / conversion module
- Digital transformation: five steps to promote enterprise progress
猜你喜欢
肠道里的微生物和皮肤上的一样吗?
Personal statement of testers from Shuangfei large factory: is education important for testers?
Unity与WebGL的相爱相杀
LeetCode142. Circular linked list II [two pointers, two methods for judging links in the linked list and finding ring points]
Matplotlib quick start
Gazebo import the mapping model created by blender
Yarn cannot view the historical task log of yarn after enabling ACL user authentication. Solution
ASP. Net core introduction V
PHP method of obtaining image information
行测-图形推理-2-黑白格类
随机推荐
Line test graph reasoning graph group class
Online interview, how to better express yourself? In this way, the passing rate will be increased by 50%~
行测-图形推理-3-对称图形类
Sword finger offer 28 Symmetric binary tree
【测试面试题】页面很卡的原因分析及解决方案
C # realizes the communication between Modbus protocol and PLC
微服务架构开源框架详情介绍
Years of summary, some core suggestions for learning programming
De la famille debezium: SET ROLE statements supportant mysql8
Debezium series: introducing support for the final operator
双非大厂测试员亲述:对测试员来说,学历重要吗?
Transparent i/o model from beginning to end
Sword finger offer 63 Maximum profit of stock
全面掌控!打造智慧城市建设的“领导驾驶舱”
Leetcode19. Delete the penultimate node of the linked list [double pointer]
Robot autonomous exploration series papers environment code
Nx10.0 installation tutorial
Robot autonomous exploration DSVP: code parsing
Unity与WebGL的相爱相杀
Debezium系列之:mysql墓碑事件