leetcode 面试经典 150 题：无重复字符的最长子串

链接	无重复字符的最长子串
题序号	3
类型	字符串
解题方法	滑动窗口
难度	中等

题目

给定一个字符串 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⁴
s 由英文字母、数字、符号和空格组成

解题

核心要点：这个问题可以通过滑动窗口的方法来解决。滑动窗口表示当前考虑的子串的范围，我们通过移动窗口的边界来找到不含有重复字符的最长子串。
- 初始化：定义两个指针 left 和 right 分别表示窗口的左右边界，以及一个哈希表 char_index_map 来存储字符及其索引。
- 扩展窗口：将 right 指针向右移动，扩展窗口，直到遇到重复的字符。
- 更新最大长度：在每次移动 right 指针时，更新不含有重复字符的子串的最大长度。
- 收缩窗口：当遇到重复的字符时，移动 left 指针，收缩窗口，直到重复的字符被移出窗口。
- 重复步骤2-4：直到 right 指针到达字符串的末尾。
时间复杂度： O(n)
空间复杂度：O(n)
c++ 实现算法：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        unordered_map<char, int> map; // 哈希表记录字符的最新索引，map 的键是字符，值是该字符的最后出现的索引位置
        int max_len = 0; // 最长子串长度
        int left = 0; // 滑动窗口的左边界

        for (int right = 0; right < s.size(); ++right) {

            // 如果当前字符在窗口内出现过，更新窗口的左边界
            //如果 map.find(s[right]) 返回的不是 map.end()，意味着哈希表中存在字符 s[right]，
            //也就是说，字符 s[right] 在哈希表中出现过。
            
            //如果返回 map.end()，则说明哈希表中没有这个字符，即字符 s[right] 没有在哈希表中出现过。
            //map[s[right]] >= left，字符 s[right] 在窗口中的 上一次出现的位置 
            //大于等于当前窗口的左边界 left，那么就说明它是重复的。
            if (map.find(s[right]) != map.end() && map[s[right]] >= left) {
                //将 left 更新为字符 s[right] 最新出现位置的下一个位置
                left = map[s[right]] + 1;
            }
            
            // 更新当前字符的最新位置
            map[s[right]] = right;
            
            // 计算当前窗口的大小，更新最大长度
            max_len = max(max_len, right - left + 1);
        }

        return max_len;
    }
};

演示：以示例1为例

遍历字符串 s，right 从 0 到 7：

right = 0，字符 ‘a’： map.find(s[right]) != map.end() 检查字符 ‘a’ 是否已经出现过。由于 map 为空，所以字符 ‘a’ 不在其中。更新哈希表：map[‘a’] = 0。字符 ‘a’ 的最新索引是 0。计算当前窗口大小：right - left + 1 = 0 - 0 + 1 = 1。更新 max_len：max_len = max(0,1) = 1。

right = 1，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 不在哈希表中。更新哈希表：map[‘b’] = 1。字符 ‘b’ 的最新索引是 1。计算当前窗口大小：right - left + 1 = 1 - 0 + 1 = 2。更新 max_len：max_len = max(1, 2) = 2。

right = 2，字符 ‘c’： map.find(s[right]) != map.end() 检查字符 ‘c’ 是否已经出现过。字符 ‘c’ 不在哈希表中。更新哈希表：map[‘c’] = 2。字符 ‘c’ 的最新索引是 2。计算当前窗口大小：right - left + 1 = 2 - 0 + 1 = 3。更新 max_len：max_len = max(2, 3) = 3。

right = 3，字符 ‘a’： map.find(s[right]) != map.end() 检查字符 ‘a’ 是否已经出现过。字符 ‘a’ 已经在 map 中，且它的索引是 0（小于 right = 3）。由于 ‘a’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘a’] + 1 = 0 + 1 = 1，新的左边界是 1，即跳过 a 在左边的位置。更新哈希表：map[‘a’] = 3。字符 ‘a’ 的最新索引是 3。计算当前窗口大小：right - left + 1 = 3 - 1 + 1 = 3。 max_len 仍然是 3（不更新）。

right = 4，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中，且它的索引是 1（小于 right = 4）。由于 ‘b’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘b’] + 1 = 1 + 1 = 2，新的左边界是 2，即跳过 b 在左边的位置。更新哈希表：map[‘b’] = 4。字符 ‘b’ 的最新索引是 4。计算当前窗口大小：right - left + 1 = 4 - 2 + 1 = 3。 max_len 仍然是 3（不更新）。

right = 5，字符 ‘c’： map.find(s[right]) != map.end() 检查字符 ‘c’ 是否已经出现过。字符 ‘c’ 已经在 map 中，且它的索引是 2（小于 right = 5）。由于 ‘c’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘c’] + 1 = 2 + 1 = 3，新的左边界是 3，即跳过 c 在左边的位置。更新哈希表：map[‘c’] = 5。字符 ‘c’ 的最新索引是 5。计算当前窗口大小：right - left + 1 = 5 - 3 + 1 = 3。 max_len 仍然是 3（不更新）。

right = 6，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中，且它的索引是 4（小于 right = 6）。由于 ‘b’ 重复了，我们需要更新滑动窗口的左边界： left = map[‘b’] + 1 = 4 + 1 = 5，新的左边界是 5，即跳过 b在左边的位置。更新哈希表：map[‘b’] = 6。字符 ‘b’ 的最新索引是 6。计算当前窗口大小：right - left + 1 = 6 - 5 + 1 = 2。 max_len 仍然是 3（不更新）。

right = 7，字符 ‘b’： map.find(s[right]) != map.end() 检查字符 ‘b’ 是否已经出现过。字符 ‘b’ 已经在 map 中，且它的索引是 6（小于 right = 7）。由于 'b’重复了，我们需要更新滑动窗口的左边界： left = map[‘b’] + 1 = 6 + 1 = 7，新的左边界是 7，即跳过 b 在左边的位置。更新哈希表：map[‘b’] = 7。字符 ‘b’ 的最新索引是 7。计算当前窗口大小：right - left + 1 = 7 - 7 + 1 = 1。 max_len 仍然是 3（不更新）。

c++ demo：

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        unordered_map<char, int> map; // 哈希表记录字符的最新索引，map 的键是字符，值是该字符的最后出现的索引位置
        int max_len = 0; // 最长子串长度
        int left = 0; // 滑动窗口的左边界

        for (int right = 0; right < s.size(); ++right) {

            // 如果当前字符在窗口内出现过，更新窗口的左边界
            //如果 map.find(s[right]) 返回的不是 map.end()，意味着哈希表中存在字符 s[right]，
            //也就是说，字符 s[right] 在哈希表中出现过。
            
            //如果返回 map.end()，则说明哈希表中没有这个字符，即字符 s[right] 没有在哈希表中出现过。
            //map[s[right]] >= left，字符 s[right] 在窗口中的 上一次出现的位置 
            //大于等于当前窗口的左边界 left，那么就说明它是重复的。
            if (map.find(s[right]) != map.end() && map[s[right]] >= left) {
                //将 left 更新为字符 s[right] 最新出现位置的下一个位置
                left = map[s[right]] + 1;
            }
            
            // 更新当前字符的最新位置
            map[s[right]] = right;
            
            // 计算当前窗口的大小，更新最大长度
            max_len = max(max_len, right - left + 1);
        }

        return max_len;
    }
};

int main() {
    Solution sol;
    string s = "abcabcbb";
    cout << "The length of the longest substring without repeating characters is: " 
         << sol.lengthOfLongestSubstring(s) << endl;
    return 0;
}