滑动窗口(2)_无重复字符的最长字串

个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

滑动窗口(2)_无重复字符的最长字串

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌

目录

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 * 104
• s 由英文字母、数字、符号和空格组成

3. 解法 :

    解法一(暴力枚举) :

    算法思路 :

枚举[从每一个位置]开始往后,无重复字符的字串可以到达什么位置.找出其中长度最大的即可.

在往后寻找无重复字串能到达的位置时,可以利用[哈希标]统计出字符出现的频次,来判断什么时候字串出现了重复元素.

    具体步骤 :

1. 定义两个指针i,j遍历数组
2. j++,向后移动寻找与i重复的数
3. j找到与i相同的数,更新字串长度.
4. 然后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,说明当前窗口没有重复元素,可以直接更新结果

基本思路:

1. left = 0, right = 0;
2. 进窗口 ------> 让字符进入哈希表
3. 循环判断
   1. 窗口内出现重复字符(提前结束循环)
   2. 出窗口 ------- > 从哈希表中删除该字符
   3. 更新结果

    图解流程:

 

 

 

 

    代码展示:

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)