题目描述：
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
数据范围:
s.length≤40000 s.length≤40000
示例：
输入：
"abcabcbb"
返回值：
3
说明：
因为无重复字符的最长子串是"abc"，所以其长度为 3。
解题思路：
本题是动态规划的经典题目。有两个解题思路。
思路一：滑动窗口
- 设计一个滑动窗口，窗口的右边界先行，用哈希表统计字符出现次数。
- 当出现重复字符时，左边界出发缩小窗口直到重复字符消失。
- 持续刷新最值就可以了。
思路二：动态规划
- 用哈希表存放字符上次出现的位置下标；用长度比字符串大1的vector，存放截止到第i个字符时，能继续维持的子串长度，比如v[0]=0，v[1]=1，v[2]可能为1可能为2。
- 执行遍历。用哈希表判断当前字符是否为重复字符，如果不是重复字符，那就在前面子串长度基础上加1；若出现了重复字符，则该字符与其重复字符的距离为i-m[s[i]]，但如果两者之间有别的重复字符，则需要考虑此类情况，可以认为在其重复字符之后的子串中，该字符未出现过，则有v[i]+1；所以，比较v[i]+1和i-m[s[i]]谁小取谁，因为小的子串没断开，后续可以继续连接，而断开的子串虽然长度大，但不可以继续增加了。
- 持续更新字符最新下标以及子串长度最大值。
测试代码：
思路一：滑动窗口
class Solution { public: // 最长子串 int lengthOfLongestSubstring(string s) { // 定义哈希表 unordered_map<char, int> m; // 滑动窗口遍历 int result = 0; for(int left = 0, right = 0; right < s.length(); ++right){ // 窗口右边界先行，统计字符出现次数 m[s[right]]++; // 当出现重复字符，窗口左边界右移缩小窗口直到重复字符消失 while(m[s[right]] > 1){ m[s[left]]--; left++; } // 持续刷新子串最大长度 result = max(result, right - left + 1); } return result; } };
思路二：动态规划
class Solution { public: // 最长子串 int lengthOfLongestSubstring(string s) { // 定义哈希表，存放的是字符出现的位置下标 unordered_map<char, int> m; int result = 0; // v[i]表示截止到i个字符时，能继续维持的子串长度 // 所以v[0]=0,v[1]=1 vector<int> v = vector<int>(s.length() + 1, 0); // i是字符串中字符下标 for(int i = 0; i < s.length(); ++i){ // 当哈希表中没发现重复字符，那就在前面最长子串长度基础上+1 if(m.find(s[i]) == m.end()) v[i + 1] = v[i] + 1; // 若出现了重复字符，该字符与其重复字符的距离为i-m[s[i]] // 但如果两者之间有别的重复字符，那要考虑这类情况 // 可以认为在其重复字符之后的子串中，该字符未出现过，则有v[i]+1 // 所以v[i]+1和i-m[s[i]]谁小，取谁，因为小的这个子串没断开 else v[i + 1] = min(v[i] + 1, i - m[s[i]]); // 刷新该字符最新下标 m[s[i]] = i; // 刷新最值 result = max(result, v[i + 1]); } return result; } };
