题目英文描述:
Given a string, find the length of the longest substring without repeating characters.
题目中文描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
思路:利用hashmap(不用hashset是为了记录下标,减少循环次数),利用滑动窗口去寻找不含重复字符的最长字串
代码:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;
int l = 0, len = 0, ans = 0;
for(int r = 0; r < s.size(); ++r) {
if(hash.find(s[r]) != hash.end() && hash[s[r]] >= l) {
//等于end()是没有, 最后一个条件是为了保证在子串中查找字符是否重复,如“abba”
//等号是子串头尾字符相等,如“pwwkew”,当r在末尾时,l=‘w’
l = hash[s[r]] + 1;
len = r - l; //计算新子串长度,两条语句顺序不能变
}
hash[s[r]] = r;
++len;
ans = max(ans, len);
}
return ans;
}
};