一、上期回顾掌握单调栈核心逻辑快速查找左右侧最值元素搞定每日温度、下一个更大元素等经典题。今天学习滑动窗口双指针经典算法解决子数组、子串、区间求和类高频考题。二、滑动窗口核心概念滑动窗口 左右双指针划定一个连续区间左指针 left窗口左边界右指针 right窗口右边界窗口不断向右滑动动态收缩左边界满足题意时间复杂度O(n)远优于暴力双重循环 O (n²)两大分类固定长度窗口窗口大小固定依次滑动统计可变长度窗口窗口大小不固定求最长 / 最短合法区间三、固定长度滑动窗口模板适用定长子数组求和、平均值、最大最小值#include iostream #include vector #include algorithm using namespace std; // 求长度为k的子数组最大和 int maxSumFixedWindow(vectorint nums, int k) { int sum 0; // 初始化第一个窗口 for(int i 0; i k; i) sum nums[i]; int max_val sum; // 滑动窗口 for(int i k; i nums.size(); i) { sum sum - nums[i - k] nums[i]; max_val max(max_val, sum); } return max_val; } int main() { vectorint arr {1,3,-1,2,5}; cout maxSumFixedWindow(arr,3); return 0; }四、可变长度滑动窗口通用核心模板通用思路右指针不断右移扩大窗口窗口不满足条件时左指针右移缩小窗口过程中记录最优答案模板框架int left 0; for(int right 0; right n; right) { // 1. 加入右边界元素更新窗口状态 // 2. 窗口不合法收缩左边界 while(窗口不满足条件) { // 移除左边界元素 left; } // 3. 记录最优答案 }五、经典例题 1最长无重复子串int lengthOfLongestSubstring(string s) { int cnt[128] {0}; int left 0, res 0; for(int right 0; right s.size(); right) { char c s[right]; cnt[c]; // 出现重复字符收缩左边界 while(cnt[c] 1) { cnt[s[left]]--; left; } res max(res, right - left 1); } return res; }六、经典例题 2最小子数组和大于目标值int minSubArrayLen(int target, vectorint nums) { int left 0, sum 0; int res 1e9; for(int right 0; right nums.size(); right) { sum nums[right]; // 满足条件就尽量缩小窗口 while(sum target) { res min(res, right - left 1); sum - nums[left]; left; } } return res 1e9 ? 0 : res; }七、滑动窗口使用禁忌滑动窗口只适用于区间具有单调性满足窗口扩张条件变松窗口收缩条件变紧不适用元素正负杂乱、无单调规律题型八、今日核心总结滑动窗口依靠左右双指针线性遍历高效解题分定长窗口与变长窗口两类题型右扩左缩先扩后缩动态维护合法区间字符串子串、数组子数组、区间统计优先用滑动窗口核心口诀右指针无脑走不合法左指针缩九、课后练习用固定窗口求数组内长度为 2 的最小和手写最长无重复子串滑动窗口代码自行实现最短子数组满足和大于给定值
滑动窗口算法：双指针高效解题秘籍
一、上期回顾掌握单调栈核心逻辑快速查找左右侧最值元素搞定每日温度、下一个更大元素等经典题。今天学习滑动窗口双指针经典算法解决子数组、子串、区间求和类高频考题。二、滑动窗口核心概念滑动窗口 左右双指针划定一个连续区间左指针 left窗口左边界右指针 right窗口右边界窗口不断向右滑动动态收缩左边界满足题意时间复杂度O(n)远优于暴力双重循环 O (n²)两大分类固定长度窗口窗口大小固定依次滑动统计可变长度窗口窗口大小不固定求最长 / 最短合法区间三、固定长度滑动窗口模板适用定长子数组求和、平均值、最大最小值#include iostream #include vector #include algorithm using namespace std; // 求长度为k的子数组最大和 int maxSumFixedWindow(vectorint nums, int k) { int sum 0; // 初始化第一个窗口 for(int i 0; i k; i) sum nums[i]; int max_val sum; // 滑动窗口 for(int i k; i nums.size(); i) { sum sum - nums[i - k] nums[i]; max_val max(max_val, sum); } return max_val; } int main() { vectorint arr {1,3,-1,2,5}; cout maxSumFixedWindow(arr,3); return 0; }四、可变长度滑动窗口通用核心模板通用思路右指针不断右移扩大窗口窗口不满足条件时左指针右移缩小窗口过程中记录最优答案模板框架int left 0; for(int right 0; right n; right) { // 1. 加入右边界元素更新窗口状态 // 2. 窗口不合法收缩左边界 while(窗口不满足条件) { // 移除左边界元素 left; } // 3. 记录最优答案 }五、经典例题 1最长无重复子串int lengthOfLongestSubstring(string s) { int cnt[128] {0}; int left 0, res 0; for(int right 0; right s.size(); right) { char c s[right]; cnt[c]; // 出现重复字符收缩左边界 while(cnt[c] 1) { cnt[s[left]]--; left; } res max(res, right - left 1); } return res; }六、经典例题 2最小子数组和大于目标值int minSubArrayLen(int target, vectorint nums) { int left 0, sum 0; int res 1e9; for(int right 0; right nums.size(); right) { sum nums[right]; // 满足条件就尽量缩小窗口 while(sum target) { res min(res, right - left 1); sum - nums[left]; left; } } return res 1e9 ? 0 : res; }七、滑动窗口使用禁忌滑动窗口只适用于区间具有单调性满足窗口扩张条件变松窗口收缩条件变紧不适用元素正负杂乱、无单调规律题型八、今日核心总结滑动窗口依靠左右双指针线性遍历高效解题分定长窗口与变长窗口两类题型右扩左缩先扩后缩动态维护合法区间字符串子串、数组子数组、区间统计优先用滑动窗口核心口诀右指针无脑走不合法左指针缩九、课后练习用固定窗口求数组内长度为 2 的最小和手写最长无重复子串滑动窗口代码自行实现最短子数组满足和大于给定值
