难度中等525
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：
s.length <= 40000
注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
哈希+滑动窗口
这道题其实是可以用动态规划的，但是对这道题可以特殊一点，因为它要求是子字符串，说明是要连续的，那么我们就可以利用滑动窗口的思想可以简化很多，原理就是控制一个区间的左右边界！
下面有两种写法，第一种的时间复杂度比较低，因为 left 是通过重复字符之间的索引位置来跳动的，而第二种方法的时间复杂度高的原因就是因为其 left 只能不断++来进行遍历！
1、第一种写法：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 划定当前窗口的坐标为(left,i],左开右闭,所以left的初始值为-1，而非0。
int left = -1;
int Max = 0; // 最大值
unordered_map<char, int> hash; // 存放最后一次字符及索引位置
for(int i = 0; i < s.size(); ++i)
{
if(hash.count(s[i]) != 0) // 出现相同字符
{
// 更新left到上一次s[i]出现的索引位置
// 当hash[s[i]] > left时，left更新为hash[s[i]],否则保持不变。
// 注意若index作为新的left，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。
left = max(hash[s[i]], left);
}
// 更新hash中s[i]出现的索引位置
hash[s[i]] = i;
Max = max(Max, i - left);
}
return Max;
}
};2、第二种写法：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> us;
int left = 0;
int Max = 0;
for(int i = 0; i < s.size(); ++i)
{
// 循环判断出现重复字符后left位置以及后面的字符
while(us.find(s[i]) != us.end())
{
us.erase(s[left]);
left++;
}
Max = max(Max, i - left + 1);
us.insert(s[i]);
}
return Max;
}
};