3-无重复字符的最长子串
@Author：CSU张扬
@Email：csuzhangyang@gmail.com or csuzhangyang@qq.com
1. 题目
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是**子串**的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
2. 解法
2.1 解法一
2.1.1 滑动窗口法：
我们依次将每个字符及其下标（从1开始，最后会解释为什么从1）存进map中。当遇到某个重复的字符 ch 时并且 m[s[i]] >= left，就把 left 设置为前一个与他重复的 ch 的value值加1，此时 (i-left+1)（i从0开始）就是上一个无重复子串的长度。
例如：jbpnbwwe
i=0, s[i]='j', left=1, m['j']=0(因为m中没有‘j’),所以将m['j'] = i+1 = 1存入map。- 同理
'b', 'p', 'n'都是插入map中。 - 此时
i=4, s[i]='b', left=1, m['b']=2 > left; 此时无重复子串长度为4("jbpn"),left值变为'b'的下一位的下标值即5; 同时更新m['b']的值为5。 - 往后同理。
2.2.2 为什么 m[s[i]] >= left，而不是 m[s[i]] > left
考虑如果当前 left 所对应的字符就是下一次重复的字符。
极端情况例如 "abbbbb"。
2.2.3 为什么 m[s[i]] = i + 1 ，而不直接等于 i？left为什么初值为1
考虑极端情况。
例如：只有一个字母 a（或者是无重复字符串 "abcd"）
假如 left=0，那么就会进入if语句中，left 会加1，而我们并没有重复的字符，left 不应该加1。
主要就是因为map中，如果没有元素c，那么 m[c] 会返回0。
执行用时 :16 ms, 在所有 cpp 提交中击败了75.44%的用户
内存消耗 :10.8 MB, 在所有 cpp 提交中击败了79.63%的用户
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 在不需要排序功能的情况下，建议使用unordered_map，它比map快。
unordered_map<char, int> m;
int max = 0;
int left = 1;
for (auto i = 0; i < s.size(); ++ i) {
if (m[s[i]] >= left) {
max = (max > (i-left+1) ? max : (i-left+1));
left = m[s[i]] + 1;
}
// 字符s[i]对应的位置为i+1,因为map不存在该元素时会返回0；
m[s[i]] = i + 1;
}
max = (max > (s.size()-left+1) ? max : (s.size()-left+1));
return max;
}
};