无重复字符的最长子串
题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）
给定一个字符串
s，请你找出其中不含有重复字符的最长子串的长度。输入:
s = "abcabcbb"输出: 3
解释: 因为无重复字符的最长子串是
"abc"，所以其长度为 3。
思路解析：
本题的暴力解法为两层for循环遍历+hash判断是否重复，时间复杂度为O(N^2)，根据暴力解法可以进一步优化将时间复杂度降低到O(N)
以示例数组为例
正向性：定义一个left和一个right指针，二者指向第一个字符。在遍历的过程中，right指针向右移动，直到遇到一个已经出现的字符停止，此时right指针是否需要回退呢？答案是不需要，因为当right指针遇到已经出现过的字符后，left指针就会开始移动，如果left++，则下一个字符为b，此时在区间(left=1)[left, right]中不存在已经重复的字符，因为已经跳过了重复的字符a。所以，left指针和right指针在移动的过程中均满足从左向右移动不回退
在上面的示例中，重复字符为第一个字符，考虑示例：s="deabcabcbb"。在该示例中，right向右移动一直到第二个字符a，此时[left, right]中存在重复字符a，停止移动right，接下来移动left，那么left是否需要一次只移动1个长度呢？不需要，原因很简单，left++后下一个区间(left=1)[left, right]起始字符为e，而对应区间中的子串为eabca，仍然存在重复字符a，所以left在移动时并不是每一次都只移动1个长度（即只循环一次），只需要让left移动到当前区间第一个重复字符的下一个字符b的位置即可，所以需要使用循环来让left一直移动直到跳过重复字符
对于哈希表的处理，不需要使用库中的结构，因为题目中给出了结果s的取值只会出现英文字母、数字、符号和空格，所以只需要定义一个长度为128的数组即可，对应的下标即为对应字符的ASCII码值
根据上面的分析，因为left和right在遍历的过程中不需要回退，所以可以考虑使用滑动窗口算法解决，步骤如下：
-
进窗口：本题进窗口意味着只要元素没有在哈希表数组中就进入哈希表数组
-
判断：因为遇到重复的字符
right就停止移动，所以当哈希表数组字符ASCII值下标对应的元素不为0即代表重复，作为判断条件 -
出窗口：出窗口则意味着已经在哈希表中的元素需要离开哈希表，并让
left向后移动，需要注意的是，因为需要进入一个新的窗口，所以出窗口时需要使left位置的字符对应哈希数组下标值的元素出现的次数改变 -
更新结果：本题更新结果只需要在
[left, right]区间没有重复字符后即可，用变量len存储子串长度，再移动right
具体步骤如下：
参考代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0}; // 创建hash表
int len = 0;
for(int left = 0, right = 0; right < s.size(); right++)
{
hash[s[right]]++; // 标记已经出现
// 判断
while(hash[s[right]] > 1)
{
hash[s[left++]]--;// 出窗口
}
len = max(len, right - left + 1);// 更新结果
}
return len;
}
};
