牛客网235698题：用滑动窗口寻找最多包含两种字符的最长子串

一、什么是滑动窗口算法？

滑动窗口算法是一种用于处理数组/字符串子区间问题的优化技术。它通过维护一个窗口（通常是子数组或子字符串），在遍历过程中动态调整窗口的边界，从而高效地解决问题。

二、算法核心思想

1. ‌初始化窗口‌：通常从数组/字符串的起始位置开始

2. ‌扩展窗口‌：移动右边界，扩大窗口范围

3. ‌收缩窗口‌：当窗口不满足条件时，移动左边界缩小窗口

4. ‌更新结果‌：在每次窗口调整后，检查是否需要更新最优解

三、完整代码

#include <iostream>
#include <string>
#include <unordered_map>
using namespACe std;

int longestSubstring(string s) {
    unordered_map<char, int> charCount; // 记录窗口中字符出现次数
    int left = 0, maxLen = 0; // 窗口左边界和最大长度
    
    for (int right = 0; right < s.size(); ++right) {
        charCount[s[right]]++; // 扩展右边界，增加当前字符计数
        
        // 当窗口内字符种类超过2时，移动左边界
        while (charCount.size() > 2) {
            charCount[s[left]]--; // 减少左边界字符计数
            if (charCount[s[left]] == 0) {
                charCount.erase(s[left]); // 如果计数为0，从哈希表中移除
            }
            left++; // 移动左边界
        }
        
        // 更新最大长度
        maxLen = max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

int main() {
    string s;
    cin >> s;
    cout << longestSubstring(s) << endl;
    return 0;
}

四、代码解析

1. ‌哈希表的使用‌：我们使用unordered_map来记录窗口中每个字符的出现次数

2. ‌双指针技巧‌：left和right指针分别表示窗口的左右边界

3. ‌窗口调整逻辑‌：

• 当哈希表中记录的字符种类超过2时，移动左指针

• 每次移动左指针时，减少对应字符的计数

• 如果字符计数减到0，从哈希表中移除该字符

五、总结

滑动窗口算法是解决子区间问题的利器，通过双指针和哈希表的配合，能够高效地处理字符串和数组问题。掌握这种算法不仅能帮助我们解决面试题，也能在实际开发中优化许多数据处理场景。