这是一个非常重要且常用的算法，主要用于处理数组/字符串的连续子元素问题。它能将嵌套循环的问题转换为单次循环，从而极大地优化时间复杂度。
一、什么是滑动窗口算法？
滑动窗口算法通过维护一个窗口（通常是数组/字符串中的一个连续子区间），在给定的规则下滑动这个窗口（扩大或缩小），从而高效地解决问题。
它本质上是一种双指针技巧，但指针的移动是单调的（通常只向右移动），因此效率很高。
核心思想：通过消除冗余的遍历操作，避免重复计算。
二、算法的基本框架
一个典型的滑动窗口算法遵循以下模式：
初始化：使用两个指针（通常是 left 和 right）来表示窗口的左右边界。初始时，它们通常都指向起始点（例如 left = 0, right = 0）。
扩大窗口：移动右指针（right++），扩大窗口 [left, right]，直到窗口中的元素满足（或不满足）某个条件。
收缩窗口：当条件被满足后，根据题意，可能需要移动左指针（left++）来收缩窗口，以寻找更优解或为下一次扩大窗口做准备。
更新结果：在扩大或收缩窗口的过程中，在合适的时机根据窗口的当前状态更新最终结果（如最大长度、最小长度、子串等）。
这个过程会持续到右指针 right 到达数组的末尾。
三、两种常见的滑动窗口类型
- 固定大小的窗口
窗口的大小是固定的。问题通常要求计算在固定窗口大小下的某个统计量（如最大值、平均值等）。
示例问题：给定一个整数数组，计算大小为 ‘k’ 的连续子数组的最大总和。
思路：
先计算第一个窗口（索引 0 到 k-1）的和。
然后，窗口向右滑动一格。新窗口的和 = 旧窗口的和 – 移出的元素（最左边） + 新加入的元素（最右边）。
在每次滑动时更新最大值。
代码示例 (Python):
python
def max_sum_subarray(arr, k):
n = len(arr)
if n < k:
return None
# 计算第一个窗口的和
window_sum = sum(arr[:k])
max_sum = window_sum
# 从第k个元素开始遍历，即窗口的右边界从 k 到 n-1
for right in range(k, n):
# 右指针右移，加上新元素
# 左指针也等效右移，减去旧元素 (right - k) 就是即将被移出窗口的左边界索引
window_sum = window_sum + arr[right] - arr[right - k]
max_sum = max(max_sum, window_sum)
return max_sum示例
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4
print(max_sum_subarray(arr, k)) # 输出 24 (子数组 [10, 2, 3, 1] 的和为 16，但 [2, 3, 1, 0, 20] 中最后4个数的和是24？ 这里需要检查：应该是子数组 [10, 2, 3, 1] -> 16)
让我们手动计算：窗口1: [1,4,2,10]=17, 窗口2: [4,2,10,2]=18, 窗口3: [2,10,2,3]=17, 窗口4: [10,2,3,1]=16, 窗口5: [2,3,1,0]=6, 窗口6: [3,1,0,20]=24。所以最大是24。
- 可变大小的窗口
窗口的大小是不固定的。问题通常要求找到满足某种条件的最长或最短的子数组/子字符串。
这是更常见的类型，也是滑动窗口的威力所在。
示例问题（LeetCode 3. 无重复字符的最长子串）：给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
思路：
使用两个指针 left 和 right 表示窗口的左右边界，初始都为 0。用一个集合（seen）来记录当前窗口中出现过的字符。
不断移动右指针 right，尝试扩大窗口。
如果新字符 s[right] 不在 seen 中，将其加入集合，并更新最大长度。
如果新字符已在 seen 中，说明出现了重复。此时需要移动左指针 left，不断从 seen 中移除 s[left] 对应的字符，直到 s[right] 这个字符被移出窗口（即重复被消除），再将 s[right] 加入集合。
重复步骤2，直到右指针到达字符串末尾。
代码示例 (Python):
python
def length_of_longest_substring(s: str) -> int:
n = len(s)
if n <= 1:
return n
left = 0
max_len = 0
seen = set()
for right in range(n):
# 当新字符已经在窗口中存在时
while s[right] in seen:
# 不断收缩左边界，直到移除那个引起重复的字符
seen.remove(s[left])
left += 1
# 将当前右指针的字符加入窗口
seen.add(s[right])
# 更新最大长度。当前窗口长度为 right - left + 1
max_len = max(max_len, right - left + 1)
return max_len示例
s = "abcabcbb"
print(length_of_longest_substring(s)) # 输出 3 ("abc")
四、滑动窗口的适用场景
当你遇到这些问题时，可以考虑使用滑动窗口：
输入是线性数据结构：如数组、链表、字符串。
问题要求寻找连续子元素的某种属性：
最长/最短子字符串
满足某些条件（如总和、无重复等）的子数组
暴力解法需要嵌套循环（通常是O(n²)或O(n³)），而滑动窗口可以将其优化为O(n)。
五、总结与技巧
核心：维护一个窗口，根据条件滑动左右指针。
关键：弄清楚什么条件下需要扩大窗口（移动右指针），什么条件下需要收缩窗口（移动左指针）。
优化：通过使用哈希表（字典）等数据结构来记录窗口状态（如字符频率、数字出现次数），可以进一步优化判断条件的速度。
时间复杂度：通常是 O(n)。虽然代码中可能有嵌套循环（如可变窗口示例中的 while），但每个元素最多被左、右指针各访问一次，所以总操作次数是 2n，依然是 O(n)。
希望这个详细的解释能帮助你彻底理解滑动窗口算法！它是解决一类高频面试题的利器，多加练习就能掌握。