前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode之Longest Substring Without Repeating Characters

LeetCode之Longest Substring Without Repeating Characters

作者头像
forrestlin
发布2018-05-24 11:26:54
4250
发布2018-05-24 11:26:54
举报
文章被收录于专栏:蜉蝣禅修之道蜉蝣禅修之道

这次的题目是找出字符串中最长不重复子串,一开始还以为跟最长匹配子串类似,需要用到动态规划呢,结果还是自己想太多了,偷看了一眼Tag,才发现只需要用hashmap和两个指针就能搞定。

算法的主要思想是:初始化两个指针head和tail,分别指向字符串初始位置0,并初始化一个hashmap,key为考察中的字符,value为对应字符所在位置。然后一个while循环,直至tail到达字符串尾部,在循环的每一步,首先会检查s[tail]是否存在于hashmap中,如果没有,则插入,否则找出s[tail]之前出现过的位置index,然后从head开始到index,逐一在hashmap中删除,然后head=index+1。最后tail++,继续循环,子串最长的长度就等于max{tail-head}。

算法的复杂度应该为N*hashmap删除元素的复杂度,应该为O(NlogN)。算法的源代码如下所示:

代码语言:javascript
复制
int lengthOfLongestSubstring(string s) {
	map<char,int>resultMap;
	int head = 0, tail = 0;
	int maxLen = 0;
	while (tail < s.length()){
		map<char,int>::iterator iter = resultMap.find(s[tail]);
		if (iter != resultMap.end()){
			if ((tail - head)>maxLen)
				maxLen = tail - head;
			int index = iter->second;
			for (int i = head; i <= index; i++){
				resultMap.erase(resultMap.find(s[i]));
			}
			head = index + 1;
		}
		resultMap.insert(pair<char, int>(s[tail], tail));
		tail++;
	}
	if (maxLen < (tail - head))
		maxLen = tail - head;
	return maxLen;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015年08月30日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档