当前位置：首页 > news >正文

滑动窗口：穿越数据的时光机

news 2025/5/12 11:08:03

在算法的世界里，滑动窗口就像是一台神奇的时光机，能够在数组或字符串等线性数据结构中高效地移动和处理数据。作为 C++ 算法小白，今天我就带大家一起探索这台神奇的时光机，看看它是如何帮助我们解决各种复杂问题的。

什么是滑动窗口？

滑动窗口是一种常用的算法技巧，主要用于处理数组或字符串中的连续子数组或子串问题。它通过维护一个固定大小或可变大小的窗口，在数据上滑动，从而高效地处理各种查询和统计问题。

滑动窗口的基本思想

窗口：窗口是数组或字符串中的一个连续区域，可以是固定大小的，也可以是可变大小的。
滑动：窗口在数据上滑动，每次滑动一个位置，根据需要调整窗口的大小。
维护信息：在窗口滑动的过程中，维护一些有用的信息，如窗口内元素的和、最大值、最小值等，从而高效地解决问题。

滑动窗口的应用场景

滑动窗口算法适用于以下类型的问题：

子数组或子串问题：如最大子数组和、最长无重复子串等。
固定大小窗口问题：如计算移动平均值、查找固定长度的子串等。
可变大小窗口问题：如最小覆盖子串、长度最小的子数组和等。

代码实现与详细解释

固定大小滑动窗口：计算移动平均值

cpp

#include <iostream>
#include <vector>using namespace std;// 计算移动平均值
vector<double> movingAverage(vector<int>& nums, int k) {vector<double> result;if (nums.empty() || k <= 0 || k > nums.size()) return result;double sum = 0;// 计算第一个窗口的和for (int i = 0; i < k; ++i) {sum += nums[i];}result.push_back(sum / k);// 滑动窗口，计算后续窗口的和for (int i = k; i < nums.size(); ++i) {sum += nums[i] - nums[i - k];  // 减去窗口左侧元素，加上窗口右侧元素result.push_back(sum / k);}return result;
}

代码解释

movingAverage 函数：计算数组中每个大小为 k 的连续子数组的平均值。首先处理边界情况，如果数组为空或 k 不合法，则直接返回空结果。
第一个窗口的和：通过遍历前 k 个元素计算第一个窗口的和，并将其平均值加入结果数组。
滑动窗口：从第 k 个元素开始，每次滑动窗口，减去窗口左侧的元素，加上窗口右侧的元素，更新和并计算平均值。

可变大小滑动窗口：最长无重复子串

cpp

#include <iostream>
#include <string>
#include <unordered_map>using namespace std;// 最长无重复子串
int lengthOfLongestSubstring(string s) {int maxLen = 0;int left = 0;unordered_map<char, int> charMap;  // 记录字符最后出现的位置for (int right = 0; right < s.length(); ++right) {// 如果字符已经在窗口中，并且出现位置在窗口左边界之后，则调整左边界if (charMap.find(s[right]) != charMap.end() && charMap[s[right]] >= left) {left = charMap[s[right]] + 1;}// 更新字符的最后出现位置charMap[s[right]] = right;// 计算当前窗口的长度maxLen = max(maxLen, right - left + 1);}return maxLen;
}

代码解释

lengthOfLongestSubstring 函数：计算字符串中最长的无重复子串的长度。使用左右指针维护一个可变大小的窗口，使用哈希表记录每个字符最后出现的位置。
调整左边界：当遇到重复字符时，调整左边界到重复字符上次出现位置的下一个位置，确保窗口内没有重复字符。
更新字符位置：每次遍历更新字符的最后出现位置，并计算当前窗口的长度，更新最大长度。

例题讲解

问题描述

给定一个字符串 s 和一个整数 k，请你找出该字符串中长度为 k 的无重复字符子串的数量。

代码示例

cpp

#include <iostream>
#include <string>
#include <unordered_map>using namespace std;// 长度为k的无重复字符子串的数量
int numKLenSubstrNoRepeats(string s, int k) {int n = s.length();if (k <= 0 || k > n) return 0;int count = 0;unordered_map<char, int> charCount;  // 记录字符在窗口中的出现次数// 初始化第一个窗口for (int i = 0; i < k; ++i) {charCount[s[i]]++;}if (charCount.size() == k) count++;  // 如果窗口中没有重复字符，则计数器加1// 滑动窗口for (int i = k; i < n; ++i) {// 移除窗口左侧的字符charCount[s[i - k]]--;if (charCount[s[i - k]] == 0) {charCount.erase(s[i - k]);}// 添加窗口右侧的字符charCount[s[i]]++;// 检查窗口中是否没有重复字符if (charCount.size() == k) count++;}return count;
}

代码解释

numKLenSubstrNoRepeats 函数：计算字符串中长度为 k 的无重复字符子串的数量。使用哈希表记录窗口中每个字符的出现次数。
初始化窗口：首先初始化第一个大小为 k 的窗口，统计其中字符的出现次数。如果窗口中没有重复字符，则计数器加 1。
滑动窗口：每次滑动窗口，移除窗口左侧的字符，添加窗口右侧的字符，并更新哈希表。如果窗口中字符的种类数等于 k，则说明窗口中没有重复字符，计数器加 1。