【算法】滑动窗口1—窗口大小固定
一、定义
滑动窗口算法（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。
图示：
第一次：（1+3+2）/3
第二次：(3+2+6)/3 ，对比上一次，少了第一个数1，多了后一个数6
第二次：(2+6-1)/3 ，对比上一次，少了上一个数2，多了后一个数-1
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
