下篇：伸缩魔法！进阶吃透可变滑动窗口篇

一、进阶趣味原理会伸缩的动态窗户上篇的固定窗口是「定死大小的玻璃窗」只能整体平移下篇的可变滑动窗口是「可拉伸的橡皮筋窗户」依旧用蜗牛场景升级理解蜗牛的窗户可以自由变大、缩小遇到合法元素就拉长身体右移right遇到非法元素就收缩尾巴右移left窗口大小动态变化适配更复杂的算法题型。核心适用场景寻找「最长子串、最短子数组、满足条件的连续区间」等无固定长度的问题是面试高频考点。二、可变滑动窗口通用模板Cint left 0; for(int right 0; right nums.size(); right){ // 1. 纳入右指针元素更新窗口状态 // 2. 窗口不合法时循环收缩左边界 while(窗口不合法条件){ // 剔除左指针元素更新窗口状态 left; } // 3. 窗口合法更新最优答案最长/最短/总数 }三、下篇4个实战案例逐行代码详解案例1无重复字符的最长子串面试必刷题目描述给定字符串找出其中不含有重复字符的最长子串长度解题思路可变窗口右指针探索新字符出现重复则收缩左窗口保证窗口内无重复#includeiostream #includestring #includeunordered_set #includealgorithm using namespace std; int lengthOfLongestSubstring(string s) { unordered_setchar st; // 存储当前窗口内的字符 int left 0, maxLen 0; for(int right 0; right s.size(); right){ // 出现重复字符收缩左窗口直到无重复 while(st.find(s[right]) ! st.end()){ st.erase(s[left]); left; } st.insert(s[right]); // 纳入新字符 maxLen max(maxLen, right - left 1); // 更新最大长度 } return maxLen; } int main(){ string s abcabcbb; cout lengthOfLongestSubstring(s) endl; // 输出3 return 0; }代码详解用哈希集合st存储当前窗口所有字符快速判断是否重复右指针遍历字符若当前字符已在集合中说明窗口重复持续删除左边界字符、右移左指针窗口无重复后纳入当前字符更新最长子串长度窗口大小动态伸缩完美适配无固定长度的最优解查找。案例2最小长度子数组和最短窗口问题题目描述给定正整数数组和目标值target找出和≥target的最短连续子数组返回其长度无则返回0解题思路可变窗口右指针累加和满足条件后不断收缩左窗口寻找最短区间#includeiostream #includevector #includealgorithm using namespace std; int minSubArrayLen(int target, vectorint nums) { int left 0, sum 0, minLen INT_MAX; for(int right 0; right nums.size(); right){ sum nums[right]; // 满足条件尝试收缩窗口找更短区间 while(sum target){ minLen min(minLen, right - left 1); sum - nums[left]; left; } } return minLen INT_MAX ? 0 : minLen; } int main(){ vectorint nums {2,3,1,2,4,3}; cout minSubArrayLen(7, nums) endl; // 输出2 return 0; }代码详解sum累加右指针元素当和≥目标值时窗口合法核心逻辑合法后持续收缩左窗口不断刷新最短长度收缩过程中实时减去左边界值保证sum实时更新最终判断是否找到合法窗口无则返回0有则返回最短长度。案例3至多两个不同字符的最长子串中等进阶题目描述给定字符串找出最多包含2个不同字符的最长子串长度解题思路哈希表统计窗口字符种类种类超2则收缩左窗口动态维护合法区间#includeiostream #includestring #includeunordered_map #includealgorithm using namespace std; int lengthOfTwoCharSub(string s) { unordered_mapchar, int mp; // 统计字符出现次数 int left 0, maxLen 0; for(int right 0; right s.size(); right){ mp[s[right]]; // 纳入新字符 // 字符种类超过2收缩窗口 while(mp.size() 2){ mp[s[left]]--; if(mp[s[left]] 0){ mp.erase(s[left]); // 次数为0移除字符 } left; } maxLen max(maxLen, right - left 1); } return maxLen; } int main(){ string s eceba; cout lengthOfTwoCharSub(s) endl; // 输出3 return 0; }代码详解哈希表mp记录窗口内每个字符的出现频次mp.size()代表字符种类数右指针纳入新字符后若种类超2循环剔除左边界字符若左边界字符频次归零从哈希表中删除保证种类统计准确窗口合法后更新最大长度实现动态伸缩求解。案例4最小覆盖子串困难压轴、面试高频题目描述给字符串s、t找出s中包含t所有字符的最小子串无则返回空串解题思路双哈希表统计字符匹配情况右指针探索全覆盖窗口左指针收缩找最小区间#includeiostream #includestring #includeunordered_map #includeclimits using namespace std; string minWindow(string s, string t) { unordered_mapchar, int need, window; // 统计t中需要的字符及数量 for(char c : t) need[c]; int left 0, valid 0; int start 0, minLen INT_MAX; for(int right 0; right s.size(); right){ char cur s[right]; if(need.count(cur)){ window[cur]; // 当前字符数量达标有效匹配数1 if(window[cur] need[cur]) valid; } // 所有字符匹配窗口全覆盖尝试收缩 while(valid need.size()){ // 更新最小窗口 if(right - left 1 minLen){ minLen right - left 1; start left; } // 收缩左边界 char leftCur s[left]; if(need.count(leftCur)){ if(window[leftCur] need[leftCur]) valid--; window[leftCur]--; } left; } } return minLen INT_MAX ? : s.substr(start, minLen); } int main(){ string s ADOBECODEBANC, t ABC; cout minWindow(s, t) endl; // 输出BANC return 0; }代码详解need存储目标字符串t的字符需求window存储当前窗口字符valid统计完全匹配的字符种类等于t的字符种类时窗口全覆盖全覆盖后收缩左窗口不断刷新最小窗口长度和起始位置收缩时若某个字符匹配失效减少有效匹配数终止收缩最终根据记录的起始位置和最小长度截取结果子串。四、上下篇核心总结思维升华上篇固定窗口窗口大小恒定先成型、再滑动适合定长区间统计、最值查找逻辑简单、容错率高下篇可变窗口窗口动态伸缩先扩张、再收缩适合最优区间求解最长/最短适配绝大多数算法面试题通用思维所有滑动窗口都是「右指针探索左指针修正」全程单次遍历摒弃暴力双层循环是区间问题的最优解思路。谢谢