对于滑动窗口第二类：窗口大小可变类型 

图解如下，类似双指针算法。

【解题思想】

1. 1、字符串 S 中使用双指针的左右指针技巧，初始化 left = right = 0，把索引的左闭右开区间 [left,right) 称为一个「窗口」。

2. 2、先不断增加 right 指针扩大窗口[left, right)（也就是 right++），直到窗口中的字符串符合要求：包含 T 中所有字符。

3. 3、停止增加 right ，转而不断增加 left 指针缩小窗口[left, right)（也就是 left++），直到窗口中的字符串不再符合要求：不包含 T 中所有字符。

4. 4、同时，每增加 left，都要更新一轮结果。

5. 5、重复 2 & 3 步骤，直到 right 到达字符串 S 的尽头。

6. 6、第 2 步骤寻找「可行解」（符合要求），第 3 步骤优化「可行解」（找最短），最终找到「最优解」（最短的覆盖子串）。

7. 7、左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」名字的来历。

例题1：最长无重复子串

【题目描述】给定一个字符串，找到最长无重复字符的子串。

【样例输入1】abcabcbb

【样例输出1】3

【样例1解释】

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

【样例输入2】bbbbb

【样例输出2】1

【样例2解释】

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

【题目分析】

(1)什么是子串？

• 子串是字符串中连续的一段字符。

• 例如，字符串 "abcabcbb" 的子串包括 "abc"、"bca"、"cbb" 等。

(2)什么是无重复字符的子串？

• 无重复字符的子串是指子串中的所有字符都是唯一的，没有重复。

• 例如，子串 "abc" 是无重复字符的，而子串 "abca" 包含重复字符 'a'。

(3)什么是最长无重复字符的子串？

• 在所有无重复字符的子串中，找到长度最长的那个。

• 例如，字符串 "abcabcbb" 的最长无重复字符子串是 "abc"，长度为 3。

【参考代码】

#include <iostream>
#include <cstring> // 用于 memset

using namespace std;

int ws(string s) {
    int n = s.size();
    int window[256]; // 用于存储字符的最近出现位置
    memset(window, -1, sizeof(window)); // 初始化为 -1
    int left = 0, right = 0; // 窗口的左右边界
    int maxLen = 0;
    while (right < n) {
        char currentChar = s[right];
        if (window[currentChar] != -1 && window[currentChar] >= left) {
            // 如果字符在窗口中，收缩左边界
            left = window[currentChar] + 1;
        }
        // 更新字符的最近出现位置
        window[currentChar] = right;
        // 更新最大长度
        maxLen = max(maxLen, right - left + 1);
        right++;
    }
    return maxLen;
}

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

【解释】

• （1）使用数组 window 存储字符的最近出现位置。

• （2）如果字符在窗口中，收缩左边界；否则，扩展右边界。

• （3）时间复杂度：O(n)。

例题2：最大子数组和

【题目描述】给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

【样例输入1】

-2,1,-3,4,-1,2,1,-5,4

【样例输出1】

6

类似题目：【算法】最大子段和 - 青少年编程知识记录

【解题思路】

1. 维护一个窗口，窗口内的元素和表示当前子数组的和。

2. 如果当前窗口的和小于 0，则丢弃当前窗口，重新开始计算。

3. 在遍历过程中，记录窗口和的最大值。

int maxSubArray(int n) {
    int maxSum = INT_MIN; // 记录最大和，初始化为最小整数值
    int currentSum = 0;   // 记录当前窗口的和
    for (int i = 0; i < n; i++) {
        currentSum += nums[i]; // 将当前元素加入窗口
        // 如果当前和大于最大和，更新最大和
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
        // 如果当前和小于 0，则丢弃当前窗口，重新开始
        if (currentSum < 0) {
            currentSum = 0;
        }
    }
    return maxSum;
}

例题3：最小覆盖子串

难度提升

【题目描述】给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回-1 

【样例输入1】

ADOBECODEBANC
ABC

【样例输出1】

BANC

【样例1解释】

最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

【样例输入2】

a
a

【样例输出2】

a

【样例2解释】

整个字符串 s 是最小覆盖子串

【样例输入3】

a
aa

【样例输出3】

-1

【样例3解释】

t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回-1

【注意】

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

• 如果 s 中存在这样的子串，我们保证它是唯一的答案。