无重复字符的最长子串
2023-03-15 22:07:18 时间
定义一个map数据结构存储(k,v),其中key值为字符,value值为字符位置+1,加1表示从字符位置后一个才开始不重复
- 我们定义不重复子串的开始位置为start,结束位置为end
- 随着end不断遍历向后,会遇到与【start,end】区间内字符相同的情况,此时将字符作为key值,获取其value值,并更新start,此时【start,end】区间内不存在重复字符
- 无论是否更新start,都会更新其map数据结构和结果ans。
- 时间复杂度:O(n)
代码:
public int lengthOfLongestSubstring(String s) {
int length=s.length();
int max=0;
//存放字符以及
Map<Character,Integer> map =new HashMap<>();
for (int start = 0,end=0; end <length ; end++) {
char element=s.charAt(end);
if (map.containsKey(element)){
//为了防止连续重复字符,这里要进行一次判断
//+1表示该元素后一个元素才是不重复字符串的开始
start=Math.max(map.get(element)+1,start);
}
max=Math.max(max,end-start+1);
//保存最后一个该结点的位置;
map.put(element,end);
}
return max;
}
相关文章
- ASP.NET Web开发框架之三 报表开发
- ASP.NET Web开发框架之二 数据输入窗体
- 甲骨文宣布JavaEE服务器WebLogic免费许可
- ASP.NET Web开发框架之一 功能导航
- 我的程序里《我的歌声里》程序员版
- Visual Studio 2012远程调试功能的改进
- PHP《个人管理系统》希望大家一起来开发
- PHP《个人管理系统》之完善登录模块
- 刘昕明:送给和我一样曾经浮躁过的PHP程序员
- 微软发布Visual Studio 2012示例代码浏览器
- 让人抓狂匪夷所思的4组代码
- 我收集到的最新的Ajax教程和技术(上篇)
- 编程赋予了我们什么样的改变
- 知识分子的傲慢与偏见
- Silverlight快速开发框架RapidSL新特性
- ASP.NET MVC3 的一个OutputCache问题
- Reactor模式及在DSS中的体现
- PHP系列学习之AOP
- 最有价值的编程忠告
- 程序员的艺术:排序算法舞蹈