【算法】滑动窗口
一、定义
滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动态调整窗口的起始和结束位置，从而高效地解决问题。
滑动窗口的核心思想是：
窗口大小固定：窗口的大小在滑动过程中保持不变。
窗口大小可变：窗口的大小根据条件动态调整。
二、使用场景
滑动窗口算法通常用于以下场景：
1.子数组/子串问题：
求满足条件的最大或最小子数组/子串。
例如：最大子数组和、最小覆盖子串、最长无重复字符子串等。
2.固定窗口大小问题：
例如：计算大小为
k的子数组的平均值。3.优化暴力解法：
将时间复杂度从
O(n²)优化到O(n)。
三、示例
1.例题1：固定窗口大小
【题目描述】给定一个数组和一个整数 k，计算所有大小为 k 的子数组的平均值。
【题目分析】
（1） 什么是子数组？
子数组是数组中连续的一段元素。
例如，数组
[1, 3, 2, 6, -1]的子数组包括[1, 3, 2]、[3, 2, 6]等。
（2）什么是大小为 k 的子数组？
大小为
k的子数组是指长度为k的连续子数组。例如，如果
k = 3，那么子数组的长度必须是 3。
（3）什么是子数组的平均值？
子数组的平均值是指子数组中所有元素的和除以子数组的长度。
例如，子数组
[1, 3, 2]的平均值是(1 + 3 + 2) / 3 = 2。
（4）问题的目标
对于数组中的每一个大小为
k的子数组，计算其平均值，并返回所有平均值的集合。
【解题思路】
（1）暴力解法
遍历数组，对于每一个起始位置
i，计算从i到i + k - 1的子数组的和，然后除以k得到平均值。时间复杂度：
O(n * k)，其中n是数组的长度。
（2）滑动窗口优化
使用滑动窗口技术，避免重复计算子数组的和。
初始化第一个窗口的和，然后在滑动窗口时，加上新元素，减去旧元素。
时间复杂度：
O(n)。
#include <iostream> using namespace std; void sw(int nums[], int n, int k) { if (n < k) return; // 如果数组长度小于k，直接返回 double windowSum = 0; // 初始化窗口 for (int i = 0; i < k; i++) { windowSum += nums[i]; } cout << windowSum / k << " "; // 滑动窗口 for (int i = k; i < n; i++) { windowSum += nums[i] - nums[i - k]; // 加上新元素，减去旧元素 cout << windowSum / k << " "; } cout << endl; } int main() { int nums[] = {1, 3, 2, 6, -1, 4, 1, 8, 2}; int n = sizeof(nums) / sizeof(nums[0]); int k = 5; sw(nums, n, k); return 0; }【过程解释】
初始化窗口：
计算第一个窗口的和
windowSum，即nums[0]到nums[k-1]的和。输出第一个窗口的平均值
windowSum / k。滑动窗口：
从第
k个元素开始，滑动窗口。每次滑动时，加上新元素
nums[i]，减去旧元素nums[i - k]。输出当前窗口的平均值
windowSum / k。
2.例题2：可变窗口大小
【题目描述】给定一个字符串，找到最长无重复字符的子串。
【题目分析】
(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)。