无重复字符的最长子串
- 难度： 中等
- 通过率： 25.7%
- 题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
解法一：滑动窗口
本题最容易想到的就是滑动窗口的解法，从左到右遍历字符串，使用一个集合保存字符，不断扩大窗口右边界，如果发现右边界的值已经存在于窗口中了，那就收缩窗口左边界。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max_len = 0;
unordered_set<char> window;
for(int lo=0,hi=0; hi < s.size(); hi++){
char ch = s[hi];
while(window.find(ch) != window.end()){
window.erase(s[lo++]);
}
window.insert(ch);
max_len = max(max_len, hi - lo + 1);
}
return max_len;
}
};
解法二：哈希表
滑动窗口在收缩窗口左边界的时候需要向后遍历，这导致算法时间复杂度为 O(n^2)，向右遍历的目的就是寻找等于 s[hi] 的值，如果能够把窗口中的值的下标记录下来，就省了内层的遍历了。
如发现了重复的字符，窗口的起始位置就要更新为先前出现的重复字符的后一个位置处。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> mp;
int start = 0;
int max_len = 0;
for(int i=0;i<s.size();i++){
char ch = s[i];
if(mp.find(ch) != mp.end()){
start = ::max(start, mp[ch] + 1);
}
mp[ch] = i;
max_len = ::max(max_len, i - start + 1);
}
return max_len;
}
};