引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记为class49的内容。滑动窗口是处理子数组（子串）问题的重要技巧，通过维持左右边界都不回退的一段范围，可以高效求解各类连续区间问题。

前置知识

学习滑动窗口之前，需要掌握以下基础知识：

双指针的基本概念
数组和字符串的基本操作
哈希表或数组的计数技巧
贪心思想的理解

049【必备】滑动窗口技巧与相关题目

基本思想

滑动窗口是通过维护一个动态区间来求解子数组或子串问题的技巧：

核心特征：左右边界都不回退（单调移动）
关键要素：找到范围和答案指标之间的单调性关系
维护信息：使用简单变量或额外结构（如数组、哈希表）来维护窗口信息
求解方式：通常固定一个边界（左或右），移动另一个边界来找答案

单调性关系

滑动窗口能够应用的前提是找到单调性：

# 示例1：累加和的单调性
# 范围变大 → 累加和一定变大（或不变）
# 范围变小 → 累加和一定变小（或不变）

# 示例2：字符种类的单调性
# 范围变大 → 字符种类一定增加（或不变）
# 范围变小 → 字符种类一定减少（或不变）

窗口维护策略

# 标准滑动窗口模板
l = 0  # 左边界
for r in range(n):  # 右边界遍历
    # 1. 扩展右边界，加入新元素
    add_element(r)
    
    # 2. 收缩左边界，维持窗口性质
    while not_valid():
        remove_element(l)
        l += 1
    
    # 3. 更新答案
    update_answer(l, r)

题目一：长度最小的子数组

问题描述

给定一个含有n个正整数的数组和一个正整数target，找到累加和≥target的长度最小的子数组并返回其长度。如果不存在符合条件的子数组返回0。

测试链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

核心思想

利用累加和的单调性质：范围变大累加和一定增加

右边界扩展：不断加入新元素增加累加和
左边界收缩：当满足条件时，尝试缩小窗口
贪心策略：在满足条件的前提下找最小长度

示例：target = 7, nums = [2,3,1,2,4,3]

初始：l=0, r=0, sum=0
r=0: sum=2, [2]
r=1: sum=5, [2,3]
r=2: sum=6, [2,3,1]
r=3: sum=8, [2,3,1,2] ✓ 满足，尝试收缩
     → 移除2，sum=6 < 7，不满足，停止收缩
     答案=4
r=4: sum=10, [3,1,2,4] ✓ 满足，收缩
     → 移除3，sum=7 ✓ 仍满足，继续
     → 移除1，sum=6 < 7，停止
     答案=min(4,3)=3
...

算法实现

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        """
        滑动窗口求最短达标子数组
        
        时间复杂度：O(n)
        - 虽然是for+while双层循环，但每个元素最多被访问两次
        - 右指针遍历n次，左指针最多移动n次
        
        空间复杂度：O(1)
        """
        ans = float('inf')  # 初始化答案为无穷大
        l = 0  # 左指针
        sum_val = 0  # 当前窗口的累加和
        
        # 右指针遍历数组
        for r in range(len(nums)):
            sum_val += nums[r]  # 右边界扩展，加入新元素
            
            # 尝试收缩左边界，保持累加和刚好 >= target
            # 贪心思想：如果去掉l位置的数还能达标，那就去掉
            while sum_val - nums[l] >= target:
                sum_val -= nums[l]  # l位置的数从窗口出去
                l += 1  # 左指针右移
            
            # 如果当前窗口满足条件，更新答案
            if sum_val >= target:
                ans = min(ans, r - l + 1)
        
        # 如果没有找到满足条件的子数组，返回0
        return 0 if ans == float('inf') else ans

算法分析

时间复杂度：O(n)（每个元素最多访问两次）
空间复杂度：O(1)
关键技巧：贪心收缩窗口

题目二：无重复字符的最长子串

问题描述

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

测试链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

核心思想

使用数组记录每个字符最后出现的位置，动态调整左边界：

位置记录：last[c]记录字符c上次出现的位置
左边界更新：遇到重复字符时，左边界跳到重复位置的下一位
答案更新：每次右边界扩展时更新最长长度

示例：s = "abcabcbb"

r=0: 'a', last['a']=-1→0, l=0, len=1
r=1: 'b', last['b']=-1→1, l=0, len=2
r=2: 'c', last['c']=-1→2, l=0, len=3
r=3: 'a', last['a']=0→3, l=max(0,0+1)=1, len=3
                          ↑重复了，左边界跳到1
r=4: 'b', last['b']=1→4, l=max(1,1+1)=2, len=3
r=5: 'c', last['c']=2→5, l=max(2,2+1)=3, len=3
...

算法实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        滑动窗口 + 位置记录
        
        核心思想：
        1. 固定窗口右边界，动态调整左边界
        2. 使用last数组记录每个字符上次出现的位置
        3. 遇到重复字符时，左边界跳到重复字符的下一个位置
        
        时间复杂度：O(n)
        空间复杂度：O(1)（last数组固定256大小）
        """
        n = len(s)
        # 记录每个字符上次出现的位置，初始化为-1表示未出现过
        last = [-1] * 256  # ASCII码范围
        ans = 0  # 记录最长子串的长度
        l = 0  # 左指针
        
        # 右指针遍历字符串
        for r in range(n):
            char_code = ord(s[r])  # 获取字符的ASCII码
            
            # 更新左指针：要么保持原位，要么跳到重复字符的下一个位置
            # 这个逻辑可以理解为：如果当前字符已经出现过，那么左边界需要跳到重复字符的下一个位置，因为不能包含重复字符
            # 如果当前字符没有出现过，那么左边界保持原位，因为可以包含重复字符
            l = max(l, last[char_code] + 1)
            
            # 更新答案
            ans = max(ans, r - l + 1)
            
            # 更新当前字符最后出现的位置
            last[char_code] = r
        
        return ans

关键点说明

# 为什么使用max(l, last[char_code] + 1)？

示例："abba"
r=0: 'a', last['a']=-1, l=max(0,-1+1)=0 ✓
r=1: 'b', last['b']=-1, l=max(0,-1+1)=0 ✓
r=2: 'b', last['b']=1,  l=max(0,1+1)=2  ✓ 左边界跳过第一个'b'
r=3: 'a', last['a']=0,  l=max(2,0+1)=2  ✓ 左边界不回退
                                          如果不用max，会错误地回到1

算法分析

时间复杂度：O(n)
空间复杂度：O(1)（256大小的数组）
优化技巧：通过位置数组避免重复扫描

题目三：最小覆盖子串

问题描述

给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串””。

测试链接：https://leetcode.cn/problems/minimum-window-substring/

核心思想

使用”欠债表”维护字符需求，先负债后还债：

欠债表：cnts[c] < 0表示还需要字符c，> 0表示字符c多余
债务管理：debt记录总债务（还需要多少个字符）
两阶段处理：先扩展找到覆盖，再收缩找到最小

示例：s = "ADOBECODEBANC", t = "ABC"

初始化欠债表：
cnts['A'] = -1 (欠1个A)
cnts['B'] = -1 (欠1个B)
cnts['C'] = -1 (欠1个C)
debt = 3

扩展阶段：
r=0: 'A', cnts['A']=-1→0, debt=3→2
r=1: 'D', cnts['D']=0→1,  debt=2
r=2: 'O', cnts['O']=0→1,  debt=2
r=3: 'B', cnts['B']=-1→0, debt=2→1
r=4: 'E', cnts['E']=0→1,  debt=1
r=5: 'C', cnts['C']=-1→0, debt=1→0 ✓ 债务还清！

收缩阶段：
去掉'A'：cnts['A']=0→-1, 不行（会欠债）
窗口："ADOBEC"，长度=6

继续扩展...

算法实现

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
        滑动窗口 + 欠债表
        
        核心思想：
        1. cnts数组维护欠债情况：
           - cnts[i] < 0：字符i有负债（还需要）
           - cnts[i] > 0：字符i有盈余（多了）
        2. debt记录总债务（还需要多少个字符）
        3. 先扩展窗口还债，债务清零后再收缩窗口
        
        时间复杂度：O(n + m)，n是s长度，m是t长度
        空间复杂度：O(1)（cnts数组固定256大小）
        """
        # 记录每种字符的欠债情况
        cnts = [0] * 256
        
        # 统计t中每个字符的需求，初始为负数（欠债）
        for char in t:
            cnts[ord(char)] -= 1
        
        length = float('inf')  # 最小覆盖子串的长度
        start = 0  # 最小覆盖子串的起始位置
        debt = len(t)  # 总债务（还需要多少个字符）
        l = 0  # 左指针
        
        # 右指针遍历字符串s
        for r in range(len(s)):
            char_code = ord(s[r])
            
            # 如果当前字符是需要的（cnts < 0），则减少债务
            if cnts[char_code] < 0:
                debt -= 1
            cnts[char_code] += 1  # 字符进入窗口
            
            # 如果债务已还清（找到了包含t所有字符的窗口）
            if debt == 0:
                # 收缩左边界，去掉多余的字符
                while cnts[ord(s[l])] > 0:
                    cnts[ord(s[l])] -= 1
                    l += 1
                
                # 更新最小窗口
                if r - l + 1 < length:
                    length = r - l + 1
                    start = l
        
        # 如果没有找到满足条件的子串，返回空字符串
        return "" if length == float('inf') else s[start:start + length]

欠债表机制详解

# 欠债表的工作原理

初始状态（t = "ABC"）:
cnts['A'] = -1  # 欠1个A
cnts['B'] = -1  # 欠1个B  
cnts['C'] = -1  # 欠1个C
其他字符 = 0     # 不欠不多

加入字符'A':
cnts['A'] = -1 + 1 = 0  # 刚好够，debt减1
加入字符'A':
cnts['A'] = 0 + 1 = 1   # 多了1个，debt不变

去掉字符'A':
cnts['A'] = 1 - 1 = 0   # 还是刚好，可以去掉
去掉字符'A':
cnts['A'] = 0 - 1 = -1  # 又欠了，不能再去掉

算法分析

时间复杂度：O(n + m)
空间复杂度：O(1)
核心技巧：欠债表 + 两阶段处理

题目四：加油站

问题描述

在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回-1。

测试链接：https://leetcode.cn/problems/gas-station/

核心思想

通过结余数组和滑动窗口找到合适的起点：

结余计算：每个位置的结余 = gas[i] - cost[i]
环路扩展：将数组扩展为两倍处理环路
窗口验证：从每个位置出发，看能否走完一圈

示例：gas = [1,2,3,4,5], cost = [3,4,5,1,2]
结余数组 = [-2,-2,-2,3,3]

扩展数组：
索引：0   1   2   3   4   5   6   7   8   9
结余：-2  -2  -2  3   3   -2  -2  -2  3   3
                          ↑原数组重复

从l=0开始：
r=0: sum=-2 < 0，失败，跳到r+1=1
从l=1开始：
r=1: sum=-2 < 0，失败，跳到r+1=2
...
从l=3开始：
r=3: sum=3 ✓
r=4: sum=6 ✓
r=5: sum=4 ✓
r=6: sum=2 ✓
r=7: sum=0 ✓
走完一圈！答案=3

算法实现

class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        """
        滑动窗口处理环路问题
        
        核心思想：
        1. 将环路扩展为两倍：[a,b,c,d,e] → [a,b,c,d,e,a,b,c,d,e]
        2. 窗口范围[l,r)，左闭右开，r是到不了的位置
        3. 从每个位置l出发，看能否走完n个站点
        4. 如果失败，直接跳到r+1位置（剪枝）
        
        时间复杂度：O(n)
        - 外层循环l最多到n-1
        - 内层循环r最多移动到2n
        - 总移动次数不超过2n
        
        空间复杂度：O(1)
        """
        n = len(gas)
        l = 0
        
        while l < n:
            r = l  # 右指针从左指针开始
            sum_val = 0  # 当前油量余额
            
            # 尝试从l位置出发
            while sum_val + gas[r % n] - cost[r % n] >= 0:
                # 检查是否已经绕了一圈
                if r - l + 1 == n:
                    return l  # 找到答案
                
                # r位置进入窗口，累加油量余额
                sum_val += gas[r % n] - cost[r % n]
                r += 1
            
            # 从l出发无法完成，直接跳到r+1开始尝试（剪枝）
            # 原理：如果从l到r失败，那么从l+1到r也必然失败
            l = r + 1
        
        return -1  # 没有找到可行的起点

剪枝原理说明

# 为什么可以直接跳到r+1？

假设从位置i到位置j失败（油量不足）：
  i → i+1 → i+2 → ... → j (失败)
  
如果从i能到j-1，说明：
  sum(i到j-1) >= 0
  
但在j失败，说明：
  sum(i到j) < 0
  即 sum(i到j-1) + rest[j] < 0
  
现在考虑从i+1出发：
  sum(i+1到j) = sum(i到j) - rest[i]
  
因为sum(i到j) < 0，且rest[i] <= sum(i到j-1)（否则到不了i+1）
所以 sum(i+1到j) <= sum(i到j) < 0

结论：从i+1、i+2...j出发都无法到达j，可以直接跳过

算法分析

时间复杂度：O(n)
空间复杂度：O(1)
核心技巧：环路扩展 + 剪枝优化

题目五：替换子串得到平衡字符串

问题描述

有一个只含有’Q’,’W’,’E’,’R’四种字符，且长度为n的字符串。假如在该字符串中，这四个字符都恰好出现n/4次，那么它就是一个「平衡字符串」。请通过「替换一个子串」的方式，使原字符串变成一个「平衡字符串」，返回待替换子串的最小可能长度。

测试链接：https://leetcode.cn/problems/replace-the-substring-for-balanced-string/

核心思想

反向思考：找到包含所有多余字符的最小窗口

字符整数化：将QWER映射为0123
计算过剩：统计每种字符超过n/4的数量
窗口覆盖：找到包含所有过剩字符的最小窗口

示例：s = "QWER", n = 4
期望：每种字符1个

示例：s = "QQWE", n = 4
Q出现2次，多1个
W出现1次，正好
E出现1次，正好
R出现0次，少1个

初始欠债表：
cnts[Q] = 1-2 = -1 (多1个Q要放进窗口)
cnts[W] = 1-1 = 0
cnts[E] = 1-1 = 0
cnts[R] = 1-0 = 1 (缺1个R，不用管)
debt = 1

找到包含这1个多余Q的最小窗口即可

算法实现

class Solution:
    def balancedString(self, s: str) -> int:
        """
        滑动窗口 + 字符整数化
        
        核心思想：
        1. 将字符映射为数字：Q→0, W→1, E→2, R→3
        2. 计算每种字符的过剩数量（超过n/4的部分）
        3. 找到包含所有过剩字符的最小窗口
        4. 这个窗口就是需要替换的最小子串
        
        时间复杂度：O(n)
        空间复杂度：O(1)（cnts数组固定4大小）
        """
        n = len(s)
        # 将字符映射为数字
        char_to_num = []
        cnts = [0] * 4  # 统计四种字符的出现次数
        
        for char in s:
            if char == 'W':
                num = 1
            elif char == 'E':
                num = 2
            elif char == 'R':
                num = 3
            else:  # 'Q'
                num = 0
            char_to_num.append(num)
            cnts[num] += 1
        
        # 计算每种字符的欠债情况
        debt = 0
        for i in range(4):
            if cnts[i] < n // 4:
                # 该字符不足，不需要减少
                cnts[i] = 0
            else:
                # 该字符过多，需要减少到n/4
                cnts[i] = n // 4 - cnts[i]  # 负数表示需要减少的数量
                debt -= cnts[i]
        
        # 如果已经平衡，直接返回0
        if debt == 0:
            return 0
        
        ans = float('inf')
        l = 0
        
        # 滑动窗口
        for r in range(n):
            # 窗口右边界向右，给出字符
            if cnts[char_to_num[r]] < 0:
                debt -= 1
            cnts[char_to_num[r]] += 1
            
            # 如果债务已还清
            if debt == 0:
                # 窗口左边界向右，拿回字符
                while cnts[char_to_num[l]] > 0:
                    cnts[char_to_num[l]] -= 1
                    l += 1
                # 更新答案
                ans = min(ans, r - l + 1)
        
        return ans

字符整数化技巧

# 为什么要字符整数化？

方法1：直接用字符作为索引（不推荐）
cnts = {}
cnts['Q'] = ...  # 字典操作，较慢

方法2：字符整数化（推荐）
cnts = [0] * 4  # 数组操作，更快
Q → 0
W → 1
E → 2
R → 3

优势：
1. 数组访问比字典快
2. 空间固定，不需要哈希表
3. 代码更清晰

算法分析

时间复杂度：O(n)
空间复杂度：O(1)
核心技巧：字符整数化 + 反向思考

题目六：K个不同整数的子数组

问题描述

给定一个正整数数组nums和一个整数k，返回nums中「好子数组」的数目。如果nums的某个子数组中不同整数的个数恰好为k，则称这个连续子数组为「好子数组」。

测试链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/

核心思想

将”恰好k种”转化为”最多k种”的差值：

核心公式：恰好k种 = 最多k种 - 最多k-1种

示例：nums = [1,2,1,2,3], k = 2

最多2种的子数组：
[1]         1种 ✓
[1,2]       2种 ✓
[2]         1种 ✓
[1]         1种 ✓
[1,2]       2种 ✓
[2]         1种 ✓
[2,1]       2种 ✓
[1]         1种 ✓
[2]         1种 ✓
[2,3]       2种 ✓
[3]         1种 ✓
...
总计：最多2种的数量 = X

最多1种的子数组：
[1]         1种 ✓
[2]         1种 ✓
[1]         1种 ✓
[2]         1种 ✓
[3]         1种 ✓
总计：最多1种的数量 = Y

恰好2种的数量 = X - Y

算法实现

class Solution:
    def subarraysWithKDistinct(self, nums: list[int], k: int) -> int:
        """
        恰好k种 = 最多k种 - 最多k-1种
        
        核心思想：
        1. "恰好k种"不好直接计算
        2. "最多k种"可以用滑动窗口
        3. 利用差值关系转化问题
        """
        return self.numsOfMostKinds(nums, k) - self.numsOfMostKinds(nums, k - 1)
    
    def numsOfMostKinds(self, arr: list[int], k: int) -> int:
        """
        计算数组中有多少子数组，数字种类不超过k
        
        核心思想：
        1. 固定右边界r，计算以r结尾的满足条件的子数组数量
        2. 对于固定的r，所有从[l,r]区间的子数组都满足条件
        3. 数量 = r - l + 1
        
        时间复杂度：O(n)
        空间复杂度：O(n)（cnts数组大小）
        """
        cnts = [0] * 20001  # 统计每个数字出现的次数
        ans = 0
        collect = 0  # 当前窗口中不同数字的种类数
        l = 0
        
        for r in range(len(arr)):
            # 右边界扩展
            cnts[arr[r]] += 1
            if cnts[arr[r]] == 1:
                collect += 1
            
            # 如果种类数超过k，收缩左边界
            while collect > k:
                cnts[arr[l]] -= 1
                if cnts[arr[l]] == 0:
                    collect -= 1
                l += 1
            
            # 以r结尾的，种类数不超过k的子数组个数
            # 例如：l=0, r=3，则子数组有[0,3],[1,3],[2,3],[3,3]
            ans += r - l + 1
        
        return ans

计数原理详解

# 为什么ans += r - l + 1？

固定右边界r，所有从[l,r]区间开始的子数组都满足条件

示例：l=1, r=4，数组=[a,b,c,d,e]
窗口内：[b,c,d,e]，种类数≤k

以r=4结尾的满足条件的子数组：
[b,c,d,e]  从1到4
[c,d,e]    从2到4
[d,e]      从3到4
[e]        从4到4

共4个，即 r - l + 1 = 4 - 1 + 1 = 4

累加过程：
r=0: ans += 1        (1个子数组)
r=1: ans += ...      (若干个子数组)
r=2: ans += ...
...
最终ans = 所有满足条件的子数组总数

转化技巧总结

# 恰好 vs 最多 转化技巧

问题类型                     转化方式
========================================================
恰好k个                   = 最多k个 - 最多k-1个
至少k个                   = 全部 - 最多k-1个
恰好在[a,b]区间内         = 最多b - 最多a-1
========================================================

这种转化技巧可以将复杂的"恰好"问题转化为
更容易处理的"最多"问题

算法分析

时间复杂度：O(n)
空间复杂度：O(n)
核心技巧：”恰好”转化为”最多”的差值

题目七：至少有K个重复字符的最长子串

问题描述

给你一个字符串s和一个整数k，请你找出s中的最长子串，要求该子串中的每一字符出现次数都不少于k。返回这一子串的长度。

测试链接：https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/

核心思想

固定字符种类 + 滑动窗口

为什么要固定字符种类？因为直接求解没有单调性：

窗口变大：字符种类可能增加，但某些字符可能不达标
窗口变小：字符种类可能减少，但剩余字符可能达标

解决方案：枚举字符种类数（1到26），对每种情况求最长子串

示例：s = "aaabb", k = 3

要求：每种字符必须出现≥3次

情况1：恰好1种字符
窗口[aaa]：'a'出现3次 ✓，长度=3

情况2：恰好2种字符
窗口[aaabb]：'a'出现3次 ✓，'b'出现2次 ✗
无满足条件的窗口

答案 = 3

算法实现

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        """
        固定字符种类 + 滑动窗口
        
        核心思想：
        1. 直接求解没有单调性，需要固定字符种类
        2. 枚举字符种类数require（1到26）
        3. 对每种情况，用滑动窗口求最长子串
        4. 维护两个指标：
           - collect: 窗口中字符种类数
           - satisfy: 达标的字符种类数（次数≥k）
        
        时间复杂度：O(26n) = O(n)
        空间复杂度：O(1)（cnts数组固定256大小）
        """
        n = len(s)
        ans = 0
        
        # 枚举字符种类数：1到26种
        for require in range(1, 27):
            cnts = [0] * 256  # 统计每个字符出现的次数
            collect = 0  # 窗口中字符种类数
            satisfy = 0  # 达标的字符种类数(次数≥k)
            l = 0
            
            # 滑动窗口
            for r in range(n):
                char_code = ord(s[r])
                cnts[char_code] += 1
                
                # 新增一种字符
                if cnts[char_code] == 1:
                    collect += 1
                # 该字符达标
                if cnts[char_code] == k:
                    satisfy += 1
                
                # 种类数超过require，收缩左边界
                while collect > require:
                    left_char_code = ord(s[l])
                    if cnts[left_char_code] == 1:
                        collect -= 1
                    if cnts[left_char_code] == k:
                        satisfy -= 1
                    cnts[left_char_code] -= 1
                    l += 1
                
                # 所有字符都达标，更新答案
                if satisfy == require:
                    ans = max(ans, r - l + 1)
        
        return ans

为什么要固定字符种类？

# 反例：不固定字符种类的问题

s = "aaabbc", k = 3

窗口扩展过程：
[a]       'a':1 ✗
[aa]      'a':2 ✗
[aaa]     'a':3 ✓  达标！
[aaab]    'a':3 ✓, 'b':1 ✗  不达标
[aaabb]   'a':3 ✓, 'b':2 ✗  不达标
[aaabbc]  'a':3 ✓, 'b':2 ✗, 'c':1 ✗  更不达标

问题：窗口变大后，新字符可能不达标
      没有明确的单调性

解决：固定字符种类后
require=1: [aaa] ✓
require=2: 无满足条件的窗口
require=3: 无满足条件的窗口

双指标维护

# collect 和 satisfy 的关系

collect: 窗口中有多少种字符
satisfy: 其中有多少种达标（出现次数≥k）

示例：s = "aabbc", k = 2, require = 2

r=0: 'a'  cnts['a']=1, collect=1, satisfy=0
r=1: 'a'  cnts['a']=2, collect=1, satisfy=1 (a达标)
r=2: 'b'  cnts['b']=1, collect=2, satisfy=1
r=3: 'b'  cnts['b']=2, collect=2, satisfy=2 (a,b都达标)
     ✓ satisfy == require，更新答案

关键判断：
if satisfy == require:  # 所有种类都达标
    ans = max(ans, r - l + 1)

算法分析

时间复杂度：O(26n) = O(n)
空间复杂度：O(1)
核心技巧：固定变量制造单调性

滑动窗口技巧总结

1. 核心模板

# 标准滑动窗口框架

def sliding_window(arr, constraint):
    """
    arr: 输入数组/字符串
    constraint: 约束条件
    """
    n = len(arr)
    l = 0  # 左指针
    ans = 初始值  # 根据题目初始化
    
    # 维护信息的数据结构（根据题目选择）
    info = {}  # 或 [], 或 变量
    
    for r in range(n):  # 右指针遍历
        # 1. 扩展右边界，更新信息
        update_info_add(arr[r])
        
        # 2. 收缩左边界，维持约束
        while not satisfy_constraint():
            update_info_remove(arr[l])
            l += 1
        
        # 3. 更新答案
        update_answer(l, r)
    
    return ans

2. 常见维护信息的方式

信息类型	数据结构	示例
计数	数组/字典	字符出现次数
位置	数组	最后出现位置
总和	变量	窗口累加和
种类	变量	不同字符数
达标数	变量	满足条件的数量

3. 滑动窗口 vs 其他技巧

# 何时使用滑动窗口？

适用情况：
✓ 连续子数组/子串问题
✓ 存在单调性关系
✓ 需要维护区间信息
✓ 左右边界都单向移动

不适用情况：
✗ 非连续子序列
✗ 需要回溯的问题
✗ 边界需要回退
✗ 需要排序的问题

4. 时间复杂度分析

# 为什么是O(n)？

虽然代码是双层循环：
for r in range(n):      # O(n)
    while ...:          # 看起来O(n)
        l += 1

但实际上：
- 右指针r：从0移动到n-1，移动n次
- 左指针l：从0移动到n-1，最多移动n次
- 总移动次数：2n次
- 时间复杂度：O(n)

关键：每个元素最多被访问常数次（进入窗口1次，离开窗口1次）

5. 常见技巧汇总

# 技巧1：位置数组避免重复扫描
last = [-1] * 256
l = max(l, last[char] + 1)  # 左边界不回退

# 技巧2：欠债表维护需求
cnts[char] = -need  # 负数表示欠债
debt = total_need   # 总债务

# 技巧3：字符整数化
char_to_num = {'Q': 0, 'W': 1, 'E': 2, 'R': 3}

# 技巧4：恰好转化为最多
exactly_k = at_most_k - at_most_(k-1)

# 技巧5：固定变量制造单调性
for require in range(1, 27):  # 固定字符种类
    # 滑动窗口求解

6. 调试技巧

# 调试检查点

1. 左右边界是否正确移动？
   - 打印l和r的值
   - 检查边界条件

2. 维护信息是否正确？
   - 打印info的内容
   - 验证更新逻辑

3. 答案更新时机是否正确？
   - 检查更新条件
   - 验证窗口状态

4. 边界情况是否处理？
   - 空数组
   - 单元素
   - 全相同元素

学习建议

1. 理解单调性

滑动窗口的核心是单调性关系：

明确范围和答案的关系
识别哪些变量具有单调性
理解如何固定变量制造单调性

2. 掌握维护技巧

熟练使用各种数据结构维护窗口信息：

数组计数（字符频次）
位置记录（避免重复扫描）
多变量跟踪（种类数、达标数等）

3. 练习转化思维

学会将复杂问题转化为简单问题：

“恰好”转化为”最多”的差值
固定变量降低问题维度
反向思考问题本质

4. 注意边界处理

重点关注边界条件：

左右边界的移动时机
答案更新的条件判断
特殊情况的处理

5. 复杂度分析

理解滑动窗口为什么是O(n)：

每个元素最多访问两次
左右指针都单向移动
总移动次数是线性的

通过掌握滑动窗口技巧，可以高效解决各类子数组和子串问题。关键在于识别单调性关系，选择合适的维护方式，以及灵活运用转化技巧。