049【必备】滑动窗口技巧与相关题目

算法讲解049【必备】滑动窗口技巧与相关题目滑动窗口算法详解一、核心概念1. 什么是滑动窗口2. 关键特征二、核心原理单调性关系三、滑动窗口的两种类型1. 固定大小窗口2. 可变大小窗口四、滑动窗口的求解流程大流程以每个位置为结尾或开头考虑基本步骤五、滑动窗口维护方式1. 简单变量维护2. 数据结构维护六、经典问题分类1. 最小覆盖子串2. 字符串排列3. 找到所有字母异位词4. 无重复字符的最长子串七、解题技巧1. 确定单调性2. 选择维护方式3. 确定收缩条件4. 更新答案时机八、实战练习建议初级题目中级题目高级题目九、常见错误与注意事项十、滑动窗口 vs 双指针滑动窗口算法详解原视频来自左神视频在这里https://www.bilibili.com/video/BV1DG411d7fh/?spm_id_from333.40164.top_right_bar_window_history.content.clickvd_source13d4a8ee0cb9348f935e4c2cc1229711一、核心概念1. 什么是滑动窗口滑动窗口是一种维护左右边界都不回退的一段范围用来高效求解子数组/子串相关问题。2. 关键特征范围不缩小左右指针通常只向右移动不回退时间复杂度通常为 O(n)比暴力 O(n²) 更高效适用场景连续子数组/子串问题二、核心原理单调性关系滑动窗口的核心关键是找到范围变化与答案指标之间的单调性关系当窗口扩大时答案指标单调变化如单调递增当窗口缩小时答案指标单调变化三、滑动窗口的两种类型1. 固定大小窗口窗口大小固定通过滑动获取所有可能的子数组// 固定窗口大小示例求大小为k的子数组最大和intmaxSumFixedWindow(vectorintnums,intk){intnnums.size();if(nk)return-1;intwindowSum0;for(inti0;ik;i){windowSumnums[i];}intmaxSumwindowSum;for(intik;in;i){windowSumwindowSumnums[i]-nums[i-k];maxSummax(maxSum,windowSum);}returnmaxSum;}2. 可变大小窗口窗口大小不固定根据条件动态调整窗口大小更常见也更具挑战性// 可变窗口通用模板voidslidingWindow(string s){unordered_mapchar,intwindow;intleft0,right0;while(rights.size()){// 扩大窗口charcs[right];right;window[c];// 满足条件时更新答案while(window needs shrink){// 缩小窗口chards[left];left;window[d]--;}}}四、滑动窗口的求解流程大流程以每个位置为结尾或开头考虑方法1更常见以每个位置为结尾考虑最佳开头 方法2以每个位置为开头考虑最佳结尾基本步骤初始化左右指针指向起点扩大窗口右指针向右移动更新窗口信息检查条件判断窗口是否满足题目要求缩小窗口左指针向右移动直到不满足条件更新答案在合适的位置记录最优解五、滑动窗口维护方式1. 简单变量维护适用于简单统计信息和、长度、计数等// 示例求和小于等于k的最长子数组长度intmaxLengthSumLessThanK(vectorintnums,intk){intleft0,right0;intcurrentSum0;intmaxLen0;while(rightnums.size()){currentSumnums[right];// 当和超过k时缩小窗口while(currentSumkleftright){currentSum-nums[left];left;}// 更新答案if(currentSumk){maxLenmax(maxLen,right-left1);}right;}returnmaxLen;}2. 数据结构维护适用于复杂统计字符频率、最值、去重等// 示例最长无重复字符子串intlengthOfLongestSubstring(string s){unordered_mapchar,intwindow;intleft0,right0;intmaxLen0;while(rights.size()){charcs[right];right;window[c];// 当窗口中有重复字符时缩小窗口while(window[c]1){chards[left];left;window[d]--;}// 更新答案maxLenmax(maxLen,right-left);}returnmaxLen;}六、经典问题分类1. 最小覆盖子串问题在字符串S中找到包含字符串T所有字符的最短子串关键用哈希表记录T中字符需求用counter记录还需匹配的字符数stringminWindow(string s,string t){unordered_mapchar,intneed,window;for(charc:t)need[c];intleft0,right0;intvalid0;// 匹配的字符数intstart0,lenINT_MAX;while(rights.size()){charcs[right];right;if(need.count(c)){window[c];if(window[c]need[c])valid;}while(validneed.size()){if(right-leftlen){startleft;lenright-left;}chards[left];left;if(need.count(d)){if(window[d]need[d])valid--;window[d]--;}}}returnlenINT_MAX?:s.substr(start,len);}2. 字符串排列问题判断字符串s2是否包含s1的排列关键固定窗口大小为s1长度滑动检查3. 找到所有字母异位词问题找到s中所有p的字母异位词的起始索引关键同排列问题记录所有符合条件的起始位置4. 无重复字符的最长子串问题找到不包含重复字符的最长子串长度关键用哈希表记录字符最后出现的位置七、解题技巧1. 确定单调性分析窗口扩大/缩小时目标函数如何变化如果窗口扩大目标函数单调递增如求和、长度如果窗口缩小目标函数单调递减2. 选择维护方式简单统计用变量维护复杂统计用哈希表、有序集合等数据结构3. 确定收缩条件明确窗口何时需要收缩和超过阈值包含重复字符包含非法字符窗口大小固定4. 更新答案时机扩张后适合求最大窗口收缩前适合求最小窗口收缩后窗口满足条件时八、实战练习建议初级题目最大连续1的个数 IIILeetCode 1004长度最小的子数组LeetCode 209水果成篮LeetCode 904中级题目最小覆盖子串LeetCode 76字符串的排列LeetCode 567找到字符串中所有字母异位词LeetCode 438高级题目K个不同整数的子数组LeetCode 992替换后的最长重复字符LeetCode 424最大连续1的个数 III进阶思考九、常见错误与注意事项指针移动顺序先移动右指针再检查条件最后移动左指针边界条件注意左右指针相等、数组为空等情况数据结构清空窗口移动时及时清理过期数据时间复杂度确保内层while循环不会导致O(n²)复杂度空间复杂度合理使用数据结构避免不必要的内存消耗十、滑动窗口 vs 双指针特性滑动窗口双指针连续性必须连续可以不连续方向通常同向可以同向或反向维护维护一个区间维护两个位置典型问题子数组/子串两数之和、三数之和滑动窗口是双指针技巧的一种特殊形式专门用于处理连续区间问题。通过掌握滑动窗口的核心思想单调性和解题流程可以解决大量子数组/子串问题。重点是多练习培养对窗口扩张/收缩条件的敏感度。