为了找到给定字符串中不含重复字符的最长子串的长度，我们可以使用滑动窗口（Sliding Window）技术配合哈希集（HashSet）来高效地处理这个问题。下面是用 C++ 来实现的详细代码和思路。

算法思路

1. 维护一个窗口：用两个指针 left 和 right 来分别表示当前窗口的左右边界。初始时，两个指针都指向字符串的开始。
2. 使用哈希集合：用一个 unordered_set 来存储当前窗口中的字符，方便快速判断字符是否重复。
3. 扩展窗口：
   • 逐渐向右移动 right 指针，向集合中添加字符。
   • 如果遇到重复字符，就通过移动 left 窗口的左指针来缩小窗口，直到没有重复字符为止。
4. 记录最大长度：在每一步中更新不重复字符子串的最大长度。

C++ 实现代码

#include <iostream>
#include <string>
#include <unordered_set>

int lengthOfLongestSubstring(const std::string& s) {
    std::unordered_set<char> char_set; // 用于存储当前窗口中的字符
    int left = 0; // 左指针
    int max_length = 0; // 保存最大长度

    for (int right = 0; right < s.length(); right++) {
        // 如果字符重复，移动左指针，直至没有重复
        while (char_set.find(s[right]) != char_set.end()) {
            char_set.erase(s[left]); // 从集合中移除左指针指向的字符
            left++; // 移动左指针
        }
        // 将当前字符添加到集合
        char_set.insert(s[right]);
        // 更新最大长度
        max_length = std::max(max_length, right - left + 1);
    }

    return max_length;
}

int main() {
    std::string s1 = "abcabcbb";
    std::cout << "Input: " << s1 << ", Output: " << lengthOfLongestSubstring(s1) << std::endl; // 输出: 3

    std::string s2 = "bbbbb";
    std::cout << "Input: " << s2 << ", Output: " << lengthOfLongestSubstring(s2) << std::endl; // 输出: 1

    std::string s3 = "pwwkew";
    std::cout << "Input: " << s3 << ", Output: " << lengthOfLongestSubstring(s3) << std::endl; // 输出: 3

    return 0;
}

代码解释

1. 数据结构：使用 unordered_set 来存储当前窗口中的字符，这样可以利用哈希表进行 O(1) 的查找。
2. 双指针遍历：
   • 使用 right 指针扩展窗口，依次遍历字符串的每个字符。
   • 当遇到重复字符时，不断移动 left 指针并从集合中移除字符，直到窗口内没有重复字符为止。
3. 更新最大长度：每次添加新字符后，更新 max_length，即有效窗口的大小是 right - left + 1。

详细分析如何通过 C++ 实现的滑动窗口算法处理输入字符串 "pwwkew"，以找到其中不含重复字符的最长子串的长度。这个过程涉及逐步跟踪两个指针（left 和 right），以及一个哈希集（unordered_set）来维护当前窗口的状态。

输入字符串

s = "pwwkew"

初始化

• left = 0：窗口的左边界。
• max_length = 0：记录最长子串的长度。
• char_set：一个空的无序集合，用于存储当前窗口的字符。

执行流程

1. 第一步：right = 0，s[right] = ‘p’

• 检查 char_set：char_set 为空，未发现重复字符。
• 将 'p' 添加到 char_set 中。
• 更新 max_length：

  max_length = max(0, 0 - 0 + 1) = 1
  

• 当前状态：

  left = 0, right = 0, char_set = {'p'}, max_length = 1
  

2. 第二步：right = 1，s[right] = ‘w’

• 检查 char_set：char_set 中没有 'w'，未发现重复字符。
• 将 'w' 添加到 char_set 中。
• 更新 max_length：

  max_length = max(1, 1 - 0 + 1) = 2
  

• 当前状态：

  left = 0, right = 1, char_set = {'p', 'w'}, max_length = 2
  

3. 第三步：right = 2，s[right] = ‘w’

• 检查 char_set：char_set 中发现 'w' 已经存在，触发重复字符处理。

• 进入 while 循环。移除 s[left] 字符：

  • 从 char_set 中移除 'p'，移动 left：

  left = 1
  char_set = {'w'}
  

• 继续检查 char_set，但 'w' 仍在集合中，继续移除。

• 移除 s[left]，即 'w'，再移动 left：

  left = 2
  char_set = {}
  

• 此时 left 已经指向 'w' 之后的位置，直接将 'w' 添加到 char_set：

• 更新 max_length：

  max_length = max(2, 2 - 2 + 1) = 2
  

• 当前状态：

  left = 2, right = 2, char_set = {'w'}, max_length = 2
  

具体分析第三步的处理过程

当前状态：

• 右指针 (right)：指向 2，即字符 s[2] = 'w'
• 字符集 (char_set)：包含 { 'p', 'w' }
• 左指针 (left)：当前为 0
• 最大长度 (max_length)：为 2

检查到重复字符

1. 当我们检查到 s[right] 为 'w' 时，首先在 char_set 中发现 'w' 已存在，这意味着当前窗口有重复字符，因此我们需要处理这个冲突。

2. 进入 while 循环：因为发现 'w' 已在集合中，我们将进入 while 循环以移除导致冲突的字符，缩小窗口。

第一步移除 ‘p’

• 从 char_set 中移除 s[left]，即 s[0] 的字符 'p'，并且 left 向右移动一位：

  char_set.erase('p'); // char_set 变为：{'w'}
  left++; // left 移动到 1
  

第二步移除 ‘w’

• 现在 left 指向字符 s[1]，即 'w'。在这个步骤中，我们的目标是继续删除字符直到没有重复为止：

• 然而，此时, 在 char_set 中，我们仍然检查到 right 指向的 'w'。

• 若要确保没有重复的字符，我们再次移除 char_set 中的字符（虽然 'w' 在集合中，但此操作并非必需，因为 'w' 现在属于右指针遇到的字符，它是被认为是"当前正在处理的字符"）。

• 从 char_set 中移除当前左边的字符 s[left]，这里移除 'w' 并增加 left：

  char_set.erase('w'); // char_set 变为空
  left++; // left 移动到 2
  

4. 第四步：right = 3，s[right] = ‘k’

• 检查 char_set：char_set 中没有 'k'，未发现重复字符。
• 将 'k' 添加到 char_set 中。
• 更新 max_length：

  max_length = max(2, 3 - 2 + 1) = 2
  

• 当前状态：

  left = 2, right = 3, char_set = {'w', 'k'}, max_length = 2
  

5. 第五步：right = 4，s[right] = ‘e’

• 检查 char_set：char_set 中没有 'e'，未发现重复字符。
• 将 'e' 添加到 char_set 中。
• 更新 max_length：

  max_length = max(2, 4 - 2 + 1) = 3
  

• 当前状态：

  left = 2, right = 4, char_set = {'w', 'k', 'e'}, max_length = 3
  

6. 第六步：right = 5，s[right] = ‘w’

• 检查 char_set：char_set 中发现 'w' 已经存在，触发重复字符处理。

• 进入 while 循环。移除 s[left] 字符：

  • 从 char_set 中移除 'k'，移动 left：

  left = 3
  char_set = {'w', 'e'}
  

• 再次检查 char_set，发现 'w' 仍在集合中，继续移除。移除 'w'：

  left = 4
  char_set = {'e'}
  

• 继续添加 s[right] 字符：

  • 将 'w' 添加到 char_set 中。

• 更新 max_length：

  max_length = max(3, 5 - 4 + 1) = 3
  

• 当前状态：

  left = 4, right = 5, char_set = {'w', 'e'}, max_length = 3
  

结果

结束遍历字符串后，最终的 max_length 为 3，表示不含有重复字符的最长子串是 "wke"，其长度为 3。

总结

在这个过程中，我们通过维护一个动态的窗口（left 和 right 指针）和使用一个集合（char_set）来高效地识别和处理重复字符，从而找到了符合条件的最长子串。每次移动指针时都确保了当前窗口内的字符是唯一的，最终得到了正确的结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符在滑动窗口中最多只被访问两次（一次添加，一次删除）。
• 空间复杂度：O(min(n, m))，其中 n 是字符串的长度，m 是字符集的大小（对于 ASCII 字符集，m 为 128）。

总结

这种方法通过滑动窗口技术高效地解决了找到不含重复字符的最长子串的问题，兼顾了性能和简单性。每一步都保持了集合的有效性，并且充分利用了数据结构的优势。