滑动窗口(2)_无重复字符的最长字串
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创滑动窗口(1)_长度最小的子数组
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 题目链接:
2. 题目描述 :
3. 解法 :
解法一(暴力枚举) :
算法思路 :
具体步骤 :
代码展示 :
结果分析 :
解法二(滑动窗口) :
算法思路 :
图解流程:
代码展示:
结果分析:
滑动窗口的正确性:
时间复杂度分析:
1. 题目链接:
OJ链接:无重复字符的最长字串
2. 题目描述 :
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
3. 解法 :
解法一(暴力枚举) :
算法思路 :
枚举[从每一个位置]开始往后,无重复字符的字串可以到达什么位置.找出其中长度最大的即可.
在往后寻找无重复字串能到达的位置时,可以利用[哈希标]统计出字符出现的频次,来判断什么时候字串出现了重复元素.
具体步骤 :
- 定义两个指针i,j遍历数组
- j++,向后移动寻找与i重复的数
- j找到与i相同的数,更新字串长度.
- 然后i++,j = i,重新重新寻找下一个数的最长无重复字串
代码展示 :
class Solution {
public:int lengthOfLongestSubstring(string s) {int len = 0, n = s.size();for(int i = 0; i < n; i++){int hash[128] = {0};for(int j = i; j < n; j++){hash[s[j]]++;if(hash[s[j]] > 1) break;len = max(len, j - i + 1); }}return len;}
};
结果分析 :
!!!!!!!!!!!!!!!!!!!!!!
居然过了?这已经是第二个算法题能直接用暴力通过了
还是老样子,分析一下题目的数据范围:
0 <= s.length <= 5 * 104字符串的长度区间范围:[0, 5*10^4],没超过10^5就给了暴力枚举的机会
我们暴力枚举的时间复杂度为O(N^2),这样数据级别大于10^9小于10^10是有机会通过的.
如果这道题更狠的话,直接把数据修改为10^5之内的字符,那我们的暴力枚举直接退役了
解法二(滑动窗口) :
算法思路 :
我们发现暴力算法真的很无脑,比如:
研究的对象依旧是一段连续的区间,因此继续使用[滑动窗口]思想来优化.
让滑动窗口满足: 窗口内所有元素都是不重复的.
做法: 右端元素right进入窗口的时候,哈希表统计这个字符的频次:
如果这个字符出现的频次超过1,说明窗口内有重复元素,那么就从左侧开始划出窗口.直到right这个元素的频次变为1,然后更新结果.
如果没有超过1,说明当前窗口没有重复元素,可以直接更新结果
基本思路:
- left = 0, right = 0;
- 进窗口 ------> 让字符进入哈希表
- 循环判断
- 窗口内出现重复字符(提前结束循环)
- 出窗口 ------- > 从哈希表中删除该字符
- 更新结果
图解流程:
代码展示:
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};int left = 0, right = 0, n = s.size();int ret = 0;while(right < n){hash[s[right]]++;while(hash[s[right]] > 1) hash[s[left++]]--;ret = max(ret, right - left + 1);right++;}return ret;}
};
结果分析:
滑动窗口的正确性:
我们这里使用滑动窗口解决了暴力枚举的重复遍历
时间复杂度分析:
时间复杂度: O(N)
空间复杂度: 我们开了一个hash数组,但只有128个空间,也就是常数级别,可以忽略不记,所以时间复杂度为O(1)