滑动窗口-无重复字符的最长子串

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 的大小。