LeetCode之Longest Substring Without Repeating Characters
这次的题目是找出字符串中最长不重复子串，一开始还以为跟最长匹配子串类似，需要用到动态规划呢，结果还是自己想太多了，偷看了一眼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;
}举报
腾讯云开发者
