【算法|滑动窗口No.3】leetcode3. 无重复字符的最长子串

拼搏现实的明天。 2024-04-27 06:53 67阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][2c60c22bffc444ada97d6b08add5486f.png]

**原题链接：[点击直接跳转到该题目][Link 3]**

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣算法分析
 *  3️⃣代码编写

## 1️⃣题目描述 ##

给定一个字符串 `s` ，请你找出其中不含有重复字符的 最长子串 的长度。

**示例1：**

> 输入: s = “abcabcbb”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

**示例2：**

> 输入: s = “bbbbb”  
> 输出: 1  
> 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

**示例3：**

> 输入: s = “pwwkew”  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。  
> 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

**提示：**

*  0 <= s.length <= 5 \*  1 0 4 10^\{4\} 104
 *  s 由英文字母、数字、符号和空格组成

## 2️⃣算法分析 ##

**遍历字符串 s，右边界 right 从 0 开始，逐步向右移动：**

*  每次将右边界对应的字符出现次数加 1，即 hash\[s\[right\]\]++，表示进窗口。
 *  判断 hash\[s\[right\]\] 是否大于 1，如果是，说明该字符重复了，需要将窗口的左边界向右移动，直到窗口中不包含重复字符，同时更新 hash 数组中左边界字符出现次数的计数。
 *  更新 ret 的值，即 ret = max(ret,right - left + 1)。

**返回 ret，即为无重复字符的最长子串的长度。**

## 3️⃣代码编写 ##

class Solution {
        
    public:
        int lengthOfLongestSubstring(string s) {
        
            int n = s.size();
            int hash[128] = {
         0 };
            int left = 0,right = 0,ret = 0;
            for(left = 0,right = 0;right < n;right++)
            {
        
                hash[s[right]]++; // 进窗口
                while(hash[s[right]] > 1) hash[s[left++]]--; // 出窗口
                ret = max(ret,right - left + 1);
            }
            return ret;
        }
    };

**最后就顺利通过啦！！!**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[2c60c22bffc444ada97d6b08add5486f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/52985efbd7924bc29890159171cf2c36.png
[Link 3]: https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/