题目链接
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目解析
我们需要找的是含重复元素的最长子串,当然直接暴力求解固然简单。但是可能引发的情况是超时,而且面试官想看到的也不是让你去暴力解决这类问题。因此我们使用哈希+滑动窗口的思想来解决。
滑动窗口+哈希
使用哈希表的缘故是更好的判断,该字符是否是重复的元素。文章来源:https://www.toymoban.com/news/detail-699904.html
将当前元素进行进窗口,如果该元素是重复的元素。那么从该窗口的左边进行出窗口,直到该元素不是重复的元素为止,每次进窗口之后统计当前无重复子串的长度,求出最长的长度并且返回,代码如下(含有详细注释)。文章来源地址https://www.toymoban.com/news/detail-699904.html
代码
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int n=s.size();
// 注意字符的范围,定义哈希表
int hash[128]={0};
int ret=0;
for(int left=0,right=0;right<n;right++)
{
// 进窗口
hash[s[right]]++;
// 若有重复元素,则进入循环
while(hash[s[right]]>1)
{
// 最左边元素出窗口
hash[s[left]]--;
// 更新窗口
left++;
}
// 走到这里right与left之间组成的字符串肯定没有重复元素
// 计算长度
ret=max(ret,right-left+1);
}
return ret;
}
};
到了这里,关于LeetCode 3. 无重复字符的最长子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!