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

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

1️⃣题目描述

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

示例1：

示例2：

示例3：

提示：

• 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;
    }
};

最后就顺利通过啦！！!