不点蓝字，我们哪来故事？
“ 别不信，求字符串最长子串用滑动窗口真不难。”
题目：leetcode 3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
子串：串中任意个连续的字符组成的子序列称为该串的子串。
解题思路
要求字符串的不含有重复字符的最长子串的长度，只需要先找到最长子串然后再求其长度即可，找最长子串我们可以通过滑动窗口的方法去查找。
滑动窗口
滑动窗口就是通过不断调整子序列的 start 和 end 位置，从而获取满足要求的结果。
具体操作如下：
- 假设已经找到一个不含重复字符子串 s[left...right]，s[left...right] 表示从字符串 s 的下标 left 到 right 的子串。
- 子串数组的右边界 right 向右移，拓展子串长度，以寻找最长子串。
- 将字符 s[right 1] 跟子串 s[left...right] 中的每个字符进行比较，如果都不同，则将字符 s[right 1] 也纳入到子串中。
- 如果字符 s[right 1] 跟子串 s[left...right] 中的某个字符相同，则将子串数组的左边界 left 右移，刨除 s[left...right] 中的那个重复的字符；
刨除前
刨除后
- left 到 right 这个区间形成一个滑动窗口，为了寻找满足条件的子串，窗口不停地在向前滑动，记录子串的长度是否是更长的子串。
细节
如何判断右边界 right 向右拓展时，其对应的字符和当前找到的子串中无重复字符呢？一个简单的方法是：设置一个数组记录 ASCII 码出现的频率，这样当 right 向右拓展时，就可以查找其对应的字符对应的 ASCII 码在该数组中相应的频率值的多少判断是否出现了重复字符。
Show me the Code
代码语言：javascript复制
// c 语言
int lengthOfLongestSubstring(char * s){
int res = 0;
int len = strlen(s);
/* 记录 ASCII 字符在子串中出现的次数 */
int freq[256] = {0};
/* 定义滑动窗口为 s[l...r] */
int l = 0, r = -1;
while (l < len) {
/* freq 中不存在该字符，右边界右移，并将该字符出现的次数记录在 freq 中 */
if (r < len - 1 && freq[s[r 1]] == 0) {
freq[s[ r]] ;
/* 右边界无法拓展，左边界右移，刨除重复元素，并将此时左边界对应的字符出现的次数在 freq 的记录中减一 */
} else {
freq[s[l ]]--;
}
/* 当前子串的长度和已找到的最长子串的长度取最大值 */
res = fmax(res, r - l 1);
}
return res;
}// c 语言
int lengthOfLongestSubstring(string s) {
int res = 0;
int len = s.size();
int freq[256] = {0};
int l = 0, r = -1;
while (l < len) {
if (r 1 < len && freq[s[r 1]] == 0) {
freq[s[ r]] ;
} else {
freq[s[l ]]--;
}
res = max(res, r - l 1);
}
return res;
}
