这次的题目是找出字符串中最长不重复子串,一开始还以为跟最长匹配子串类似,需要用到动态规划呢,结果还是自己想太多了,偷看了一眼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)。算法的源代码如下所示:
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;
}