LeetCode 3 无重复字符的最长子串
🟡 中等
https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
先给答案分类， 再加上最优性质， 再思考之间的关系.
s = “abcabcbb”
以c结尾的和前面以b结尾的有什么关系? 显然以b结尾的最长子串加上c之后可能会出现重复， 一定是和c发生重复， 所以移动左端点， 直到不重复。
- 如何判断重复. 可以使用hash表，
char:count， hash表的大小等于 左右之间的个数时就是不重复， 否则重复了， 移动左端点直到 hash大小等于 左右之间的长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> hash_map;
int left = 0;
int ans =0;
for(int right = 0;right<s.size();right++){
hash_map[s[right]]++;
while(hash_map.size()<(right-left+1)){
hash_map[s[left]]--;
if(hash_map[s[left]]==0) hash_map.erase(s[left]);
left++;
}
// cout<<hash_map.size();
//
ans = max(ans,static_cast<int>(hash_map.size()));
}
return ans;
}
};