徐州网站建设大前端,天津网站建设座机号,北京官网seo,免费网络课程教学平台作者#xff1a;翟天保Steven 版权声明#xff1a;著作权归作者所有#xff0c;商业转载请联系作者获得授权#xff0c;非商业转载请注明出处 题目描述#xff1a;
请从字符串中找出一个最长的不包含重复字符的子字符串#xff0c;计算该最长子字符串的长度。
数据范围…作者翟天保Steven 版权声明著作权归作者所有商业转载请联系作者获得授权非商业转载请注明出处 题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串计算该最长子字符串的长度。
数据范围: s.length≤40000 s.length≤40000 示例
输入
abcabcbb返回值
3说明
因为无重复字符的最长子串是abc所以其长度为 3。 解题思路
本题是动态规划的经典题目。有两个解题思路。
思路一滑动窗口
设计一个滑动窗口窗口的右边界先行用哈希表统计字符出现次数。当出现重复字符时左边界出发缩小窗口直到重复字符消失。持续刷新最值就可以了。
思路二动态规划
用哈希表存放字符上次出现的位置下标用长度比字符串大1的vector存放截止到第i个字符时能继续维持的子串长度比如v[0]0v[1]1v[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_mapchar, 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_mapchar, int m;int result 0;// v[i]表示截止到i个字符时能继续维持的子串长度// 所以v[0]0,v[1]1vectorint v vectorint(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;}
};
