算法 - 滑动窗口专项
核心：同向双指针，利用 "数组元素均为正数" 这一条件，通过右指针扩展、左指针收缩的方式，将暴力 O(n²) 优化到 O(n)。
一、基础知识点
1. 最小长度子数组（LeetCode 209）
题目描述
给定正整数数组和一个目标值 target，找出最短的连续子数组，使其和 ≥ target，若不存在则返回 0。
核心思路
利用正数性质——向右扩展时，结果是递增的。
右指针不断右移，把元素累加进 sum
左指针收缩：当 sum - nums[left] ≥ target 时，说明去掉 left 元素后仍满足条件，左指针右移
每次满足条件时更新最小长度
复杂度
时间：O(n)（左右指针各最多移动 n 次）
空间：O(1)
Python 实现
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums) # 获取数组长度
ans = float('inf') # 初始化答案为无穷大（用于取最小值）
s = 0 # 当前窗口内元素和
left = 0 # 左指针初始化为0
# 枚举右指针，不断扩大窗口
for right in range(n):
s += nums[right] # 将右指针指向的元素加入窗口
# 尝试收缩左指针：当去掉左元素后仍满足条件，就继续收缩
# 关键点：利用正数性质，若窗口和 - 左元素 >= target，
# 说明收缩后仍满足条件，可以放心收缩
while s - nums[left] >= target:
s -= nums[left] # 从总和中移除左指针指向的元素
left += 1 # 左指针右移，收缩窗口
# 更新最短长度：当窗口和 >= target 时记录答案
# right - left + 1 是因为 left 和 right 都是闭区间的索引
if s >= target:
ans = min(ans, right - left + 1)
# 如果 ans 没被更新过，说明不存在满足条件的子数组，返回0
return ans if ans != float('inf') else 0
2. 乘积小于 K 的子数组（LeetCode 713）
题目描述
给定正整数数组和一个整数 K，计算乘积小于 K 的连续子数组的个数。
核心思路
和上一题类似，右指针不断扩展，左指针收缩保证乘积 < K。
关键是计数公式：以 right 为右端点，满足条件的子数组个数 = right - left + 1
（若 left 到 right 乘积 < K，则 left 到 right、left+1 到 right… 共 right-left+1 个都满足）
复杂度
时间：O(n)
空间：O(1)
Python 实现
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
# 边界情况：k <= 1 时，正整数乘积不可能小于1，返回0
if k <= 1:
return 0
ans = 0 # 累计满足条件的子数组个数
s = 1 # 当前窗口内元素的乘积（用1初始化）
left = 0 # 左指针
# 枚举右指针
for right, x in enumerate(nums):
s *= x # 将右指针指向的元素乘入窗口乘积
# 收缩左指针：直到乘积小于 K 为止
# 注意：用除法是因为 nums[left] 是正整数
while s >= k:
s //= nums[left] # 移除左指针指向元素的贡献
left += 1 # 左指针右移
# 关键计数公式：
# 以 right 为右端点，左指针为 left 的窗口内，
# 任意以 right 为右端点、向左扩展的子数组都满足条件
# 个数 = 窗口内元素个数 = right - left + 1
# 例如：left=0, right=2 时，有 [0~2], [1~2], [2~2] 共3个
ans += right - left + 1
return ans
3. 无重复字符的最长子串（LeetCode 3）
题目描述
找出字符串中不含重复字符的最长子串，返回其长度。
核心思路
用哈希表记录每个字符出现的次数。
右指针扩展，把字符加入窗口
若某字符出现次数 > 1，说明窗口内有重复，左指针收缩直到该字符出现次数 = 1
维护最大长度
复杂度
时间：O(n)
空间：O(1)（字符集有限，ASCII 128 或 256）
Python 实现
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0 # 记录最长长度
count = Counter() # 哈希表：字符 -> 出现次数
left = 0 # 左指针
# 枚举右指针
for right, x in enumerate(s):
count[x] += 1 # 将当前字符加入窗口，出现次数+1
# 若该字符出现次数 > 1，说明窗口内有重复字符
# 需要收缩左指针，直到该字符出现次数恢复为1
while count[x] > 1:
count[s[left]] -= 1 # 移除左指针指向的字符
left += 1 # 左指针右移
# 更新最长长度：当前窗口 [left, right] 无重复，长度为 right-left+1
ans = max(ans, right - left + 1)
return ans
二、练习
1. 每个字符最多出现两次的最长子字符串 🔢
题目描述（LeetCode 3090 - 简单）
给你一个字符串 s，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。
示例
输入：s = “bcbbbcba”
输出：4
解释：“bcbb”（或 “cbbc” 或 “bbbc” 或 “bbcb”）每个字符最多出现两次，长度为 4。
解题思路
滑动窗口 + 哈希表记录字符出现次数。
右指针扩展，字符计数 +1
若计数 > 2，左指针收缩直到该字符计数 ≤ 2
维护最大长度
复杂度
时间：O(n)
空间：O(1)
Python 代码
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
n = len(s) # 字符串长度
left = 0 # 左指针初始化
count = Counter() # 哈希表：字符 -> 出现次数
ans = 0 # 记录最大长度
# 枚举右指针
for right, x in enumerate(s):
count[x] += 1 # 将当前字符加入窗口
# 若该字符出现次数超过2，收缩左指针直到恢复正常
while count[x] > 2:
count[s[left]] -= 1 # 移除左指针指向的字符
left += 1 # 左指针右移
# 更新最大长度
ans = max(ans, right - left + 1)
return ans
2. 最多 K 个重复元素的最长子数组 🔢
题目描述（LeetCode 2958 - 中等）
给你一个整数数组 nums 和一个整数 k。
一个元素 x 在数组中的频率指的是它在数组中的出现次数。
如果一个数组中所有元素的频率都小于等于 k，那么我们称这个数组是好数组。
请你返回 nums 中最长好子数组的长度。
子数组指的是一个数组中一段连续非空的元素序列。
示例
输入：nums = [1,2,3,1,2,3,1,2], k = 2
输出：6
解释：最长好子数组是 [1,2,3,1,2,3]，值 1、2 和 3 在子数组中的频率都没有超过 k = 2。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。最长好子数组的长度为 6。
解题思路
和上题同一套路，只是把 "字符出现不超过 2 次" 泛化成 "出现次数不超过 k"。
右指针扩展，元素计数 +1
若该元素计数 > k，左指针收缩直到该元素计数 ≤ k
维护最大长度
复杂度
时间：O(n)
空间：O(n)
Python 代码
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
n = len(nums) # 数组长度
left = 0 # 左指针
ans = 0 # 记录最大长度
dic = defaultdict(int) # 哈希表：元素值 -> 出现次数
# 枚举右指针
for right, x in enumerate(nums):
dic[x] += 1 # 将当前元素加入窗口
# 若该元素出现次数超过 k，收缩左指针直到恢复正常
while dic[x] > k:
dic[nums[left]] -= 1 # 移除左指针指向的元素
left += 1 # 左指针右移
# 更新最大长度
ans = max(ans, right - left + 1)
return ans
3. 最长的半重复子字符串 🧩
题目描述（LeetCode 2730 - 中等）
给你一个下标从 0 开始的字符串 s，这个字符串只包含 0 到 9 的数字字符。
如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是半重复的。例如，“0010”、“002020”、“0123”、“2002” 和 “54944” 是半重复字符串，而 “00101022”（相邻的相同数字对是 “00” 和 “22”）和 “1101234883”（相邻的相同数字对是 “11” 和 “88”）不是半重复字符串。
请你返回 s 中最长半重复子字符串的长度。
示例
输入：s = “52233”
输出：4
解释：最长的半重复子字符串是 “5223”。整个字符串 “52233” 有两个相邻的相同数字对 “22” 和 “33”，但最多只能选取一个。
解题思路
这题稍有不同，统计的是相邻相同字符对的数量。
用 cnt 记录当前窗口内有多少对相邻相等
右指针右移时，若 s[right] == s[right-1]，cnt++
若 cnt > 1，左指针收缩，同时如果 left 与 left+1 相等要 cnt–
维护最大长度
复杂度
时间：O(n)
空间：O(1)
Python 代码
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
n = len(s) # 字符串长度
left = 0 # 左指针
cnt = 0 # 窗口内相邻相等字符对的数量
ans = 1 # 初始化为1（单字符一定是半重复的）
# 枚举右指针（从1开始，因为需要和前一个字符比较）
for right in range(1, n):
# 若当前字符与前一个字符相等，窗口内多了一对相邻相等
if s[right] == s[right - 1]:
cnt += 1
# 若相邻相等对超过1对，收缩左指针直到恢复正常
while cnt > 1:
# 收缩前先检查左指针和left+1是否相等，
# 若相等则移出窗口后这对就不存在了，需要减1
if s[left] == s[left + 1]:
cnt -= 1
left += 1
# 更新最大长度
ans = max(ans, right - left + 1)
return ans
三、滑动窗口总结 ✨
适用条件
数组 / 字符串的连续子区间问题
满足某种单调性：扩大窗口条件更易满足 / 缩小窗口条件更易不满足
固定套路
右指针 for 循环扩展
while 循环内左指针收缩（根据具体条件）
更新答案
时间复杂度分析
不要被二重循环吓住——左指针最多移动 n 次，右指针也是 O(n)，总复杂度 O(n)。
关键点
乘积类问题：K ≤ 1 直接返回 0（正数乘积不可能小于 1）
计数类问题：以 right 为右端点的满足条件的子数组数 = right - left + 1
相邻字符对问题：用额外变量追踪相邻相等的情况