滑动窗口-无重复字符的最长子串
1.引入：
滑动窗口是数组/字符串问题中常用的抽象概念。
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，
即 [i, j)[i,j)（左闭，右开）。
而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。
例如，我们将 [i, j)[i,j) 向右滑动 11 个元素，
则它将变为 [i+1, j+1)[i+1,j+1)（左闭，右开）。
2.代码实现：
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<set>
#include<map>
using namespace std;
string s;
int ans=0;
set<char> ss;
int main(){
cin>>s;
int len=s.length();
int i=0,j=0;
while(i<len && j<len){
if(ss.find(s[j]) != ss.end()){
//说明找到有子字符包含了
ss.erase(s[i]);
i++;
} else {
ss.insert(s[j]);
j++;
ans=max(ans,j-i);
}
}
cout<<ans<<endl;
return 0;
} 3.复杂度分析：
A. 时间复杂度：O(2n) = O(n)O(2n)=O(n)，在最糟糕的情况下，每个字符将被 ii 和 jj 访问两次。
B. 空间复杂度：O(min(m, n))O(min(m,n))，与之前的方法相同。
滑动窗口法需要 O(k)O(k) 的空间，其中 kk 表示 Set 的大小。
而 Set 的大小取决于字符串 nn 的大小以及字符集 / 字母 mm 的大小。
查看5道真题和解析