【LeetCode滑动窗口专题#2】无重复字符的最长子串
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
思路
容易想到这里需要使用滑动窗口的思想来解决问题
我们可以定义两个指针，left和right
left一开始指向0，right则放入for循环中向前不断遍历字符串s
这里还需要维护一个哈希表（选择map，因为字符类型不止有26个字母）
使用当前遍历值（字符）在表中查询，如果没出现过，就把当前字符放入哈希表中
注意！！！！！！
这里有可能我们会下意识的将哈希表的键值结构定义为："遍历字符--字符出现次数"
在本题中，这是错误的，或者说是不合适的
因为我们需要找到重复字符第一次出现的位置，如以字符出现次数为值的话，无法实现这一目的（字符出现位置可以帮助我们确定哪个字符是第一个不重复的字符）
举个例子，假设有字符串 "abccba"，如果我们以字符出现次数为值来构建哈希表，那么哈希表的值应该为 {'a': 2, 'b': 2, 'c': 2}，这些字符的出现次数都是相同的。如果我们想要找到第一个不重复的字符，就需要进一步遍历原字符串，找到第一个出现次数为1的字符。但是，如果我们以字符出现位置为值来构建哈希表，那么哈希表的值应该为 {'a': 0, 'b': 1, 'c': 2}，我们可以在遍历字符串的过程中实时更新哈希表，并找到第一个出现位置最小的字符。
因此，在这个问题中，以字符为键，以字符出现位置为值（"遍历字符--字符首次出现位置"）是更加合适的选择。
继续
如果当前遍历值在表中出现过，那么我们在哈希表中获取该字符对应的值，即其在s中第一次出现的位置
将左指针移动到该位置（为什么？），并且加1跳过该位置，目的是剔除重复值
这里是本题的第二个坑
在写的时候，第一版中我移动left时用了left++，但是这样是错的，不能简单地使用left++来移动左指针，因为有可能之前的某个字符已经出现过，那么我们需要更新左指针的位置，使得新的左指针位置可以舍弃之前出现过的字符，从而保证当前的子串不重复。
这其实还涉及到我们如何定义“重复出现”这件事情
因为在设计hash表时，保存的是当前字符的索引，因此，我们仅仅在hash中查询到某个字符还不够，原因如下：
如果当前字符s[right]已经在哈希表中存在，则说明该字符之前出现过，我们需要更新左指针的位置，使其跳过该重复字符，即左指针left的新位置应该是(hash[s[right]]+1)。但是，在更新左指针的同时，还需要确保新的左指针位置大于等于上一个子串的起始位置left，因为我们要寻找最长的无重复子串，而不仅仅是子串长度。
因此，
hash.find(s[right]) != hash.end() && hash[s[right]] >= left确保了字符s[right]曾经出现过（也就是该字符在哈希表中有对应的索引），并且其最后一次出现的下标大于等于当前子串的起始位置left，才会更新左指针的位置。如果只写
hash.find(s[right]) != hash.end()的话，可能会把之前的那些已经被跳过的字符再次算进去，从而导致错误的结果。例如："abcabcbb"
如果当前左指针指向的是第一个b，右指针指向第二个a，说明我们已经判断a重复出现，并把左指针移动到了hash[s[right]]+1
此时我们并没有删除hash表中关于a第一次出现的位置信息，因此下一次如果还遇到a，我们不能让左指针移动到第一次a的位置
所以需要加上限定条件，即
hash[s[right]] >= left来保证左指针的正常跳转
然后，更新当前字符在哈希表中的位置值，即将当前字符位置设置为第一次出现位置
代码
关键点：哈希表键值对设计（采用"遍历字符--字符首次出现位置"）、left指针的移动方式
步骤：
1、定义一个哈希表，键为字符，值为字符出现的index
2、移动右指针遍历字符串s，在哈希表中查询当前遍历字符
? 如果有重复，同时判断该重复值位置是否大于left指针位置（因为如果出现重复值，left指针所值的应该是上一次该值出现的位置），大于则将left移动到当前字符位置，并加1跳过当前位置
? 如果无重复，先不处理
3、不管有无重复都对当前遍历字符在哈希表中的值（即位置索引）进行更新（同时也处理了无重复的情况）
4、左右指针作差与最大长度变量比较，并更新该变量
5、返回最大长度变量
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;//创建hash表
int left = 0;//左指针
int maxLen = 0;
for(int right = 0; right < s.size(); ++right){//遍历字符串s
if(hash.find(s[right]) != hash.end() && left <= hash[s[right]]){//若当前字符在哈希表中存在
left = hash[s[right]] + 1;//获取当前字符在哈希表中对应的值，该值为字符在s中的索引，将左指针移动到此处
//即若当前字符在哈希表中存在，我们需要将left指针指到重复字符s[right]上次出现的位置，然后加1来跳过它
}
//对应情况：1、当前字符在哈希表中不存在/2、跳转left指针至重复值第一次出现位置之后，更新当前字符在哈希表中的位置信息
hash[s[right]] = right;//添加字符到哈希表/更新信息
if(right - left + 1 > maxLen) maxLen = right - left + 1;//更新当前最大长度
}
return maxLen;
}
};