【练习】【滑动窗口】力扣热题100 3. 无重复字符的最长子串

题目

3. 无重复字符的最长子串

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

示例 1:

输入: s = “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”

输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣热题100 3. 无重复字符的最长子串

思路（注意事项）

整体思路

这段代码使用了滑动窗口算法来解决计算字符串中最长无重复字符子串长度的问题。滑动窗口由两个指针 i 和 j 定义，i 作为右指针不断向右移动，扩大窗口范围，同时将字符及其出现次数记录在 mp 中。当发现某个字符的出现次数大于 1 时，说明窗口内出现了重复字符，此时通过移动左指针 j 缩小窗口范围，直到窗口内不再有重复字符。在这个过程中，不断更新最长无重复字符子串的长度。

具体步骤

1. 初始化：
   • 创建一个 map<char, int> 类型的 mp 用于记录字符的出现次数。
   • 初始化 len 为 0，用于存储最长无重复字符子串的长度。
   • 初始化双指针 i 和 j 都为 0，分别作为右指针和左指针。
2. 右指针移动：
   • 右指针 i 从 0 开始遍历字符串 s，每遍历一个字符，将该字符在 mp 中的出现次数加 1。
3. 处理重复字符：
   • 当 mp[s[i]] > 1 时，说明当前字符 s[i] 在窗口内出现了重复，需要移动左指针 j 来缩小窗口。
   • 每次移动左指针 j 时，将 mp[s[j]] 减 1，直到 mp[s[i]] 等于 1，即窗口内不再有重复字符。
4. 更新最长子串长度：
   • 每次移动右指针 i 后，计算当前窗口的长度 i - j + 1，并与 len 比较，取较大值更新 len。
5. 返回结果：
   • 遍历完整个字符串后，返回 len，即最长无重复字符子串的长度。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串的长度。右指针 i 会遍历字符串一次，左指针 j 最多也只会遍历字符串一次，因此总的时间复杂度为线性的。

纯代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> mp;
        int len = 0;
        for (int i = 0, j = 0; i < s.size(); i ++){
            mp[s[i]] ++;
            while (mp[s[i]] > 1) mp[s[j]] --, j ++;
            len = max (len, i - j + 1);
        }
        return len;
    }
};

题解（加注释）

#include <string>
#include <map>
#include <algorithm>

class Solution {
public:
    // 该函数用于计算字符串 s 中最长无重复字符子串的长度
    int lengthOfLongestSubstring(std::string s) {
        // 定义一个字符到整数的映射 mp，用于记录每个字符在当前子串中出现的次数
        std::map<char, int> mp;
        // 初始化最长无重复字符子串的长度为 0
        int len = 0;

        // 使用双指针法，i 为右指针，j 为左指针，初始都指向字符串的起始位置
        for (int i = 0, j = 0; i < s.size(); i++) {
            // 右指针 i 指向的字符出现次数加 1
            mp[s[i]]++;

            // 当右指针 i 指向的字符出现次数大于 1 时，说明当前子串中出现了重复字符
            while (mp[s[i]] > 1) {
                // 左指针 j 指向的字符出现次数减 1
                mp[s[j]]--;
                // 左指针 j 右移一位，缩小当前子串的范围
                j++;
            }

            // 计算当前无重复字符子串的长度，并更新最长无重复字符子串的长度
            len = std::max(len, i - j + 1);
        }

        // 返回最长无重复字符子串的长度
        return len;
    }
};