网站 建设 领导小组,a5网站诊断,做网站发违规内容 网警抓不抓,中国广告公司目录
一、滑动窗口的核心原理
二、滑动窗口的两种类型
1. 固定大小的窗口
2. 可变大小的窗口
三、实现细节与关键点
1. 窗口的初始化
2. 窗口的移动策略
3. 结果的更新时机
四、经典问题与代码示例
示例 1#xff1a;和 ≥ target 的最短子数组#xff08;可变窗口…目录
一、滑动窗口的核心原理
二、滑动窗口的两种类型
1. 固定大小的窗口
2. 可变大小的窗口
三、实现细节与关键点
1. 窗口的初始化
2. 窗口的移动策略
3. 结果的更新时机
四、经典问题与代码示例
示例 1和 ≥ target 的最短子数组可变窗口
示例 2无重复字符的最长子串哈希表辅助
五、边界条件与易错点
1. 数组越界
2. 初始值的设置
3. 哈希表的使用
4. 循环条件错误
六、时间复杂度分析
七、滑动窗口的适用场景
八、滑动窗口的扩展
1. 结合前缀和
2. 结合单调队列
总结 一、滑动窗口的核心原理 滑动窗口Sliding Window 是一种基于 双指针Two Pointers 的算法设计范式核心思想是通过维护一个 动态窗口区间[left, right]在遍历过程中调整窗口的左右边界避免重复计算从而将时间复杂度优化到 O(n)。 核心逻辑 窗口扩张right 指针向右移动扩大窗口直到满足某个条件。 窗口收缩一旦满足条件left 指针向右移动缩小窗口直到不满足条件。 更新结果在窗口调整过程中记录最优解。 二、滑动窗口的两种类型
1. 固定大小的窗口 特点窗口长度固定为 k通过滑动窗口的起始位置遍历所有可能的子区间。 典型问题 求长度为 k 的子数组的最大平均值 长度为 k 的子字符串的排列匹配
C 代码模板
int fixedWindow(vectorint nums, int k)
{int sum 0, max_sum 0;// 初始化窗口for (int i 0; i k; i) sum nums[i];max_sum sum;// 滑动窗口for (int right k; right nums.size(); right) {sum nums[right] - nums[right - k]; // 窗口右移更新和max_sum max(max_sum, sum);}return max_sum;
}
2. 可变大小的窗口 特点窗口大小不固定根据问题条件动态调整 left 和 right 指针。 典型问题 无重复字符的最长子字符串 和大于等于 target 的最短子数组
C 代码模板
int variableWindow(string s)
{unordered_mapchar, int window;int left 0, max_len 0;for (int right 0; right s.size(); right) {char c s[right];window[c]; // 窗口扩张// 窗口收缩条件出现重复字符while (window[c] 1) {char d s[left];window[d]--; // 移出左边界字符left;}max_len max(max_len, right - left 1); // 更新结果}return max_len;
} 三、实现细节与关键点
1. 窗口的初始化 初始指针位置通常 left right 0。 状态变量如窗口内的和sum、哈希表记录字符频率等。
2. 窗口的移动策略 扩张条件一般通过 for 循环逐步移动 right。 收缩条件在满足特定条件时通过 while 循环移动 left直到条件不满足。
3. 结果的更新时机 固定窗口每次窗口滑动后更新结果。 可变窗口在窗口收缩后或扩张过程中更新结果。 四、经典问题与代码示例
示例 1和 ≥ target 的最短子数组可变窗口
int minSubArrayLen(int target, vectorint nums)
{int left 0, sum 0;int min_len INT_MAX;for (int right 0; right nums.size(); right) {sum nums[right]; // 窗口扩张while (sum target) { // 窗口收缩条件min_len min(min_len, right - left 1);sum - nums[left]; // 窗口收缩}}return min_len INT_MAX ? 0 : min_len;
}
示例 2无重复字符的最长子串哈希表辅助
int lengthOfLongestSubstring(string s)
{unordered_mapchar, int last_pos; // 记录字符最后出现的位置int left 0, max_len 0;for (int right 0; right s.size(); right) {char c s[right];// 若字符 c 已存在且在窗口内移动 left 到 last_pos[c] 1if (last_pos.count(c) last_pos[c] left) {left last_pos[c] 1;}last_pos[c] right; // 更新字符位置max_len max(max_len, right - left 1);}return max_len;
} 五、边界条件与易错点
1. 数组越界 在固定窗口中需确保 right - k 0。 在可变窗口中需检查 left 是否超过 right。
2. 初始值的设置 最小值初始化为 INT_MAX最大值初始化为 INT_MIN。
3. 哈希表的使用 在字符频率统计中需确保哈希表的键存在性如用 count() 检查。
4. 循环条件错误 错误在收缩窗口时使用 if 而非 while导致窗口未完全收缩。 正确使用 while 循环确保窗口收缩到条件不满足。 六、时间复杂度分析 固定窗口O(n)每个元素被访问一次。 可变窗口O(n)每个元素最多被 left 和 right 各访问一次。 七、滑动窗口的适用场景 连续子数组/子字符串问题 最短/最长满足条件的子数组 子数组的和/乘积/频率统计 优化暴力解法 将 O(n²) 的暴力枚举优化为 O(n) 数据流处理 实时处理数据流中的窗口统计量如移动平均值 八、滑动窗口的扩展
1. 结合前缀和 用于处理负数数组或更复杂的条件如子数组和为 k。 示例代码 int subarraySum(vectorint nums, int k)
{unordered_mapint, int prefix_sum; // 前缀和 - 出现次数prefix_sum[0] 1;int sum 0, count 0;for (int num : nums) {sum num;if (prefix_sum.count(sum - k)) {count prefix_sum[sum - k];}prefix_sum[sum];}return count;
}
2. 结合单调队列 用于维护窗口内的最大值/最小值如滑动窗口最大值问题。 示例代码 vectorint maxSlidingWindow(vectorint nums, int k)
{dequeint dq; // 存储下标按值单调递减vectorint res;for (int i 0; i nums.size(); i) {// 移除超出窗口的元素if (!dq.empty() dq.front() i - k) dq.pop_front();// 维护单调队列while (!dq.empty() nums[i] nums[dq.back()]) dq.pop_back();dq.push_back(i);// 记录窗口最大值if (i k - 1) res.push_back(nums[dq.front()]);}return res;
} 总结
滑动窗口的核心在于 双指针的协同移动 和 窗口状态的动态维护。掌握以下要点 明确窗口的 扩张与收缩条件。 合理选择 数据结构如哈希表、单调队列维护窗口状态。 注意 边界条件 和 初始值设置。 灵活结合其他算法如前缀和、单调队列解决复杂问题。
