首页 > 代码库 > Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters
这题看起来挺简单的，就是存一个哈希表<char, 字符位置>，然后依次遍历整个字符串，遇到前面有过的字符的时候，就该停止当前计数，新的子串应该从发现该字符的位置的下一位置开始。
我开始写了一个简单的写法，发现超时了：
if (s.empty()) return 0; if (s.length() == 1) return 1; int longest = 1; for (int i = 0; i < s.length(); i++){ int len = 0; unordered_map<char, int> substr; int index = i; while (i < s.length() && (substr.find(s[i]) == substr.end() || substr.find(s[i])->second == index) ){ if (substr.find(s[i]) == substr.end()){ substr[s[i]] = i; len++; } else { substr[s[i]] = i; } i++; } if (len > longest) longest = len; if (i < s.length()){ i = substr.find(s[i])->second + 1; } //i = index; } return longest;我这里的问题是发现重复字符的时候，字串指针不应该回溯，这是很浪费的！
其实只需要修改字串开始位置就可以了。还有就是哈希表要随时存储某字符的最右边的位置。
int lengthOfLongestSubstring(string s) { if (s.empty()) return 0; if (s.length() == 1) return 1; unordered_map<char, int> charIndex; int start = 0; int longest = 1; int len = 1; charIndex[s[0]] = 0; for (int i = 1; i < s.length(); i++){ if (charIndex.find(s[i]) == charIndex.end()){ charIndex[s[i]] = i; len++; } else{ if (charIndex[s[i]] > start){ if (len > longest) longest = len; len -= charIndex[s[i]] - start; start = charIndex[s[i]] + 1; } else if (charIndex[s[i]] == start){ start += 1; } else { len++; } charIndex[s[i]] = i; } } if (len > longest) longest = len; return longest; }
Longest Substring Without Repeating Characters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。