3 无重复字符的最长子串
和其他滑动窗口子串问题不同: - 本题没有使用两个子串s和t - 比较的子串没有重复字符,这意味着不需要使用valid和need
为什么使用滑动窗口 -> 因为题目问的是子串,即连续字符序列
判断字符是否重复 -> 用哈希表维护滑动窗口的字符
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
int len = 0;
while(right < s.size()){
char c = s[right];
right++;
window[c]++;
while(window[c] > 1){
char d = s[left];
left++;
window[d]--;
}
// 更新结果在收缩外,因为收缩表示还有重复字符
// 结果统计的是没有重复字符的情况
len = max(len, right - left);
}
return len;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
int start = 0;
unordered_set<char> hashMap;
int ans = 0;
for(int end = 0; end < n; end++){
while(hashMap.count(s[end])){
// 这里注意是把s[start]移除
hashMap.erase(s[start]);
start++;
}
hashMap.insert(s[end]);
ans = max(ans,end - start + 1);
}
return ans;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)