模块二——滑动窗口:3.无重复字符的最长子串
2023-12-13 03:44:32
文章目录
题目描述
题目链接:3.无重复字符的最长子串
算法原理
解法?:暴?求解(不会超时,可以通过)
枚举从每?个位置开始往后,?重复字符的?串可以到达什么位置。找出其中?度最?的即可。
在往后寻找?重复?串能到达的位置时,可以利?哈希表统计出字符出现的频次,来判断什么时候?串出现了重复元素。
解法二:滑动窗口
研究的对象依旧是?段连续的区间,因此继续使?滑动窗?思想来优化。
让滑动窗?满?:窗?内所有元素都是不重复的。
做法:右端元素ch进?窗?的时候,哈希表统计这个字符的频次:
- 如果这个字符出现的频次超过1 ,说明窗?内有重复元素,那么就从左侧开始划出窗?,直到ch 这个元素的频次变为1 ,然后再更新结果。
- 如果没有超过1 ,说明当前窗?没有重复元素,可以直接更新结果。
代码实现
解法?:暴?求解(时间复杂度为O(N2),空间复杂度为O(1))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;//记录结果
for(int left = 0;left < s.size();left++)
{
int hash[128] = { 0 };//记录每个字母的出现次数
for(int right = left;right < s.size();right++)
{
hash[s[right]]++;
if( hash[s[right]] > 1)
{
break;
}
res = max(res,right - left + 1);
}
}
return res;
}
};
解法二:滑动窗口(时间复杂度为O(N),空间复杂度为O(1))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = { 0 };//记录每个字母的出现次数
int res = 0;//记录结果
for(int left = 0,right = 0;right < s.size();right++)//1.控制窗口的左右指针
{
hash[s[right]]++;//2.进窗口
while(hash[s[right]] == 2)//3.判断
{
//出窗口
hash[s[left]]--;
left++;
}
res = max(res,right - left + 1);
}
return res;
}
};
文章来源:https://blog.csdn.net/quantian_/article/details/134960769
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!