每日算法之LeetCode 3:Longest Substring Without Repeating Characters
LeetCode 3：Longest Substring Without Repeating Characters（最长不含重复字符的子串）
Q:Given a string, find the length of the longest substring without repeating characters.
我是翻译君:
给定一个字符串，找到不含重复字符的最长子串
1.可能需要和面试官沟通的问题
这里的字符是只含有字母还是字母加数字，还是ASCII的所有字符集
2.话不多说，开始分析啦
如果没有思路的话，暴力法肯定是可以解决的。那么这里我就不说这种解法了。讲道理，有点嫌了哈哈。
如果你看了我上一篇文章:
那么你肯定可以很容易想到一种解法，没错了，就是滑动窗口。很明显这题的一个很好的解法就是用滑动窗口。
没看过也没关系，这里放一张分析图，紫色区域就是我们说的"滑动窗口"。
4.就凭这个一小窗口就可以解决问题？是可以的，那么端好小板凳，拿好小本本，下面划重点了
（1）定义滑动窗口的区间[l,r],初始为[0,-1],也即是区间无元素
（2）初始化最大子串长度为0
（3）定义一个数组存储字符元素的重复出现的次数
（4）开始滑动窗口，窗口为出界并且当r指针指向的字符未出现时候，r指针右移。当r指针指向的字符不是第一次出现时候，l指针右移。
（5）最后利用max函数找到最长的子串
int lengthOfLongestSubstring(string s) {
int l=0;
int r=-1; //1.定义滑动窗口的区间[l,r],初始为[0,-1],也即是区间无元素
int len=0; //2.最大子串长度
int freq[256]={0}; //3.定义一个数组存储字符元素的重复出现的次数
//开始滑动窗口
while(l<s.size()){
if(r+1<s.size()&&freq[s[r+1]]==0){ //窗口为出界并且当r指针指向的字符未出现时候，r指针右移
r++;
freq[s[r]]++;
}
else{
freq[s[l]]--; //r指针指向的字符不是第一次出现时候，l指针右移
l++;
}
len=max(len,r-l+1); //找到最长的子串
}
return len;
}
这里面有个小技巧，怎么样只利用O（1）的时间复杂度求出一段字符串里某个字符没有重复呢？
没错，就是上面的一个长度为256的数组
int freq[256]={0};
因为字符肯定都是在ASCII编码里，共256个，那么扫描到某个字符时，就会对应到该字符的ASCII码，也就会对应成数组的下标了。初始话所有字符出现次数都为0，如果扫描到一次，对应的次数就加1.
freq[s[r+1]]==0
通过这个字符在数组的值是否为0来判断是否出现过，从而让窗口进行移动（缩小或扩大）
到这里是不是发现滑动窗口的魅力，真的是很厉害的一种解题方式了。