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

个人主页：兜里有颗棉花糖
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由兜里有颗棉花糖原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

原题链接：点击直接跳转到该题目

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 * $10^{4}$
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;
    }
};