目录
前言
1. 无重复字符的最长子串
2. 题目解析
3. 算法原理
解法1：暴力枚举 + 哈希表（判断字符是否有重复出现）
解法2：滑动窗口
4. 代码
前言
当我们发现暴力解法两个指针都不回退，都是向同一个方向移动的时候我们就可以使用滑动窗口
1. 无重复字符的最长子串
题目链接：
3. 无重复字符的最长子串 - 力扣（LeetCode）
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
2. 题目解析
以示例1为例：
其他两个示例也相同，都是按照不含有重复字符的最长字串的长度
3. 算法原理
解法1：暴力枚举 + 哈希表（判断字符是否有重复出现）
时间复杂度：O（n^2）
定义两个指针left（表示每次枚举的起始位置）和right（往后去找最多能到哪里）
定义一个hash表，用来帮助我们保存这段区间字符的信息，right往后走的时候如果不在哈希表里就放进表里，继续往后走，如果在表里就停止
当我们发现right遇到重复字符的时候，我们先让left跳过重复字符（下标为2的a，并不是right指向的a）指向重复字符的后面一位
因为不这样的话即使right回到本次枚举的位置（b）也会在遇到重复字符a再次停下，这段区间里的长度是一定小于上一次的
然后接下来right就没有回到本次枚举指向的位置（b）的必要了，因为我们的left跳过了重复字符，所以这段区间里是一定没有重复字符的，所以right++即可
到这里我们发现暴力解法两个指针都不回退，都是向同一个方向移动的时候我们就可以使用滑动窗口
解法2：滑动窗口
利用上面的规律，使用滑动窗口来解决问题
1. 定义两个指针left和right来充当窗口的左端点和右端点，然后用left和right来标记窗口的左区间和右区间
2. 进窗口：让字符进入哈希表
3. 判断：当窗口里出现重复字符时
4. 根据判断再看是否出窗口：从哈希表里删除字符
出窗口就是让left右移，进窗口就是让right右移
本题的更新结果是在整个判断结束之后更新
4. 代码
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int hash[128] = { 0 }; // 使⽤数组来模拟哈希表
int left = 0, right = 0, n = s.size();
int ret = 0;
while (right < n)
{
hash[s[right]]++; // 进⼊窗⼝
while (hash[s[right]] > 1) // 判断
hash[s[left++]]--; // 出窗⼝
ret = max(ret, right - left + 1); // 更新结果
right++; // 让下⼀个元素进⼊窗⼝
}
return ret;
}
};未完待续~
