剑指offer(C++)-JZ48：最长不含重复字符的子字符串(算法-动态规划)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

数据范围:

 s.length≤40000 s.length≤40000

示例：

输入：

"abcabcbb"

返回值：

3

说明：

因为无重复字符的最长子串是"abc"，所以其长度为 3。 

解题思路：

本题是动态规划的经典题目。有两个解题思路。

思路一：滑动窗口

1. 设计一个滑动窗口，窗口的右边界先行，用哈希表统计字符出现次数。
2. 当出现重复字符时，左边界出发缩小窗口直到重复字符消失。
3. 持续刷新最值就可以了。

思路二：动态规划

1. 用哈希表存放字符上次出现的位置下标；用长度比字符串大1的vector，存放截止到第i个字符时，能继续维持的子串长度，比如v[0]=0，v[1]=1，v[2]可能为1可能为2。
2. 执行遍历。用哈希表判断当前字符是否为重复字符，如果不是重复字符，那就在前面子串长度基础上加1；若出现了重复字符，则该字符与其重复字符的距离为i-m[s[i]]，但如果两者之间有别的重复字符，则需要考虑此类情况，可以认为在其重复字符之后的子串中，该字符未出现过，则有v[i]+1；所以，比较v[i]+1和i-m[s[i]]谁小取谁，因为小的子串没断开，后续可以继续连接，而断开的子串虽然长度大，但不可以继续增加了。
3. 持续更新字符最新下标以及子串长度最大值。

测试代码：

思路一：滑动窗口

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]=1vector<int> v = vector<int>(s.length() + 1, 0);// i是字符串中字符下标for(int i = 0; i < s.length(); ++i){// 当哈希表中没发现重复字符，那就在前面最长子串长度基础上+1if(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]]谁小，取谁，因为小的这个子串没断开elsev[i + 1] = min(v[i] + 1, i - m[s[i]]);// 刷新该字符最新下标m[s[i]] = i;// 刷新最值result = max(result, v[i + 1]);}return result;}
};