61. 最长不含重复字符的子字符串
题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
假设字符串中只包含从 a 到 z 的字符。
数据范围
输入字符串长度 [0,1000]。
样例
输入:"abcabc"
输出:3
算法1 双指针
双指针算法特征:第一个指针往后移的时候第二个指针也是往后移的,单调
算法流程
枚举右端点,出现重复值时动态调整左端点
时间复杂度
$O(n)$
i最多走过n,j最多走过n
C++ 代码
y总的极简代码
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
unordered_map<char, int> count;
int res = 0;
for(int i = 0, j = 0; j < s.size(); j++) //遍历右边界,调整左边界
{
if(++count[s[j]] > 1) //出现重复时必然是在右边界
{
//调整左边界,一致移动以定位重复元素
while(count[s[i]] == 1) count[s[i++]]--;
count[s[i++]]--; //将重复元素移出窗口
}
res = max(res, j - i + 1);
}
return res;
}
};
基础版的滑动窗口
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
if(!s.size()) return 0;
unordered_map<char, int> window;
int res = 0, l = 0, r = 0;
while(r < s.size())
{
char c = s[r];
r++;
window[c]++;
while(window[c] > 1)
{
char d = s[l];
l++;
window[d]--;
}
res = max(res, r - l);
}
return res;
}
};
总结
知道应该用双指针-滑动窗口,但是写不出来,就离谱