题目内容
给定一个字符串，请你找出其中不含有重复字符的
最长子串的长度。
示例 1:
输入:
"abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为3。
示例 2:
输入:
"bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。
示例 3:
输入:
"pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
如果我是面试官
这个题目是中等难度, 这个题目还是有几个细节需要注意. 编码的时候要留心.
题目分析
- 快慢指针
- 滑动窗口
- hash
这里用到了hash, hash的作用是做一个倒排索引, 方便根据字符找到该字符对应的下标.
python 版本解答
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
table = dict()
slow = 0
fast = 0
ret_max = 0
while slow<len(s) and fast<len(s):
# find dup, slide window
if s[fast] in table :
slow = max(table[s[fast]],slow)
del(table[s[fast]])
#table[s[fast]] = slow
else:
table[s[fast]] = fast
fast+=1
ret_max = max(ret_max,fast-slow-1)
return ret_max
c++版本解答
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// sliding windows
int ret{0};
int fast = 0;
int slow = 0;
int max = 0;
map<char,int> hashmap;
while(slow < s.length() && fast< s.length()){
auto map_it = hashmap.find(s[fast]);
// find dup
if(map_it!=hashmap.end()) {
hashmap.erase(s[slow]);
slow++;
} else{
hashmap[s[fast]] = fast;
fast++;
max = std::max(fast-slow,max);
}
}
return max;
}
};
