滑动窗口算法：从零到精通，一文搞定所有套路！+ LeetCode高频考点：滑动窗口算法详解与解题模板
“面试官让我找出字符串中最长无重复子串，我用了两层循环，O(n²)的时间复杂度，面试官摇了摇头。然后他问：‘知道滑动窗口吗？’——那一刻我才明白，我与大厂offer之间，只差一个滑动窗口的距离。”
滑动窗口（Sliding Window），这个听起来有些神秘的名字，其实是解决数组/字符串子区间问题的利器。无论是字节跳动高频出现的“最小覆盖子串”，还是腾讯常考的“长度最小的子数组”，滑动窗口都能以O(n)的时间复杂度优雅解决。今天，我就带你从零开始，彻底掌握这个让算法面试变简单的核心技巧！
1. 为什么要学滑动窗口？（解决痛点）
先看一个经典问题
LeetCode 209. 长度最小的子数组
给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其和≥ target的长度最小的连续子数组，并返回其长度。
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
暴力解法思路（最直观的想法）
- 枚举所有可能的子数组
- 计算每个子数组的和
- 找出满足条件的最短子数组
// 暴力解法 O(n²) int minSubArrayLen_brute(int target, vector<int>& nums) { int n = nums.size(); int minLen = INT_MAX; // 枚举所有起始位置 for (int i = 0; i < n; i++) { int sum = 0; // 枚举所有结束位置 for (int j = i; j < n; j++) { sum += nums[j]; if (sum >= target) { minLen = min(minLen, j - i + 1); break; // 找到了就break，因为后面的更长 } } } return minLen == INT_MAX ? 0 : minLen; }暴力解法的问题分析
数组：[2, 3, 1, 2, 4, 3] 目标：sum ≥ 7 暴力解法过程： i=0: [2], [2,3], [2,3,1], [2,3,1,2] → 找到，长度=4 i=1: [3], [3,1], [3,1,2], [3,1,2,4] → 找到，长度=4 i=2: [1], [1,2], [1,2,4] → 找到，长度=3 i=3: [2], [2,4], [2,4,3] → 找到，长度=3 i=4: [4], [4,3] → 找到，长度=2 ⭐ i=5: [3] → 不满足 时间复杂度：O(n²) 当 n=10000 时，需要约 1亿 次操作超时，严重超时了！！！
滑动窗口的优化思路
观察：窗口的连续性
假设我们有一个窗口 [2,3,1] 和为6 < 7 传统做法：丢弃整个窗口，从3重新开始 聪明做法：为什么不只丢弃左边的2，保留 [3,1] 呢？ 当前窗口：[2,3,1] 和=6 < 7 扔掉左边：移除2 → [3,1] 和=4 加入右边：加入2 → [3,1,2] 和=6 加入右边：加入4 → [3,1,2,4] 和=10 ≥ 7 这样避免了重复计算 [3,1] 的和！滑动窗口的核心思想
就像相机取景框，只移动边界，不重新拍摄整个画面
初始： [2,3,1,2,4,3] 窗口： |---| ← 和=6 < 7 left right 扩大窗口： |-----| ← 加入2，和=8 ≥ 7 收缩窗口： |-----| ← 去掉2，加入... 寻求更短的int minSubArrayLen_sliding(int target, vector<int>& nums) { int left = 0; // 窗口左边界 int sum = 0; // 当前窗口的和 int minLen = INT_MAX; // 最小长度 int n = nums.size(); for (int right = 0; right < n; right++) { // 1. 加入右边元素（扩大窗口） sum += nums[right]; // 2. 当窗口满足条件时，尝试收缩窗口 while (sum >= target) { // 更新最小长度 minLen = min(minLen, right - left + 1); // 收缩窗口：移除左边元素 sum -= nums[left]; left++; } // 3. 如果窗口不满足条件，继续扩大窗口（下一轮循环） } return minLen == INT_MAX ? 0 : minLen; }数组：[2, 3, 1, 2, 4, 3] 目标：sum ≥ 7 暴力解法计算过程： i=0: 2 → 5 → 6 → 8 ✔ i=1: 3 → 4 → 6 → 10 ✔ i=2: 1 → 3 → 7 ✔ i=3: 2 → 6 → 10 ✔ i=4: 4 → 7 ✔ i=5: 3 总共计算了 3+4+3+3+2+1 = 16 次加法 滑动窗口计算过程： 初始化: sum=0 right=0: sum=2 right=1: sum=5 right=2: sum=6 right=3: sum=8 (≥7) → minLen=4, sum=6, left=1 right=4: sum=10 (≥7) → minLen=3, sum=7, left=2 right=5: sum=10 (≥7) → minLen=2, sum=6, left=3 总共计算了 6 次加法 + 3 次减法 = 9 次运算先向右扩大，当sum足够时，再从左缩小
2. 滑动窗口的核心思想
四大核心理念
1. 连续性原则
// 只处理连续的子序列，不是任意的子集 ✅ [1,2,3,4] 中的 [2,3,4] // 连续，可以用滑动窗口 ❌ [1,2,3,4] 中的 [1,3,4] // 不连续，不能用滑动窗口2. 单调移动原则
// 左右指针只能单向移动（通常向右） int left = 0, right = 0; while (right < n) { // right只会增加 // left只会增加或不变 // 永远不会回头！ }3. 局部更新原则
// 窗口从 [2,3,1] 滑动到 [3,1,2] // 传统方法：重新计算 3+1+2 = 6 // 滑动窗口：利用已有的 2+3+1=6，然后： new_sum = old_sum - 离开的元素 + 新进入的元素 = 6 - 2 + 2 = 6 // 只计算变化的部分！4. 最优性保证原则
// 通过合理的收缩规则，确保不会错过最优解 while (窗口不满足条件) { 收缩窗口; // 剔除"坏"元素 } // 此时窗口是当前右边界下的"局部最优"3.leetcode题目
1.代码实现：
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_set<char> charSet; int left = 0, maxLen = 0; for (int right = 0; right < s.size(); right++) { while (charSet.find(s[right]) != charSet.end()) { charSet.erase(s[left]); left++; } charSet.insert(s[right]); maxLen = max(maxLen, right - left + 1); } return maxLen; } };set 是 C++ STL 中的一种关联容器，它存储唯一的元素（不允许重复），并且元素会自动排序。
#include <set> #include <unordered_set> // 有序集合（基于红黑树实现） set<int> orderedSet; // 无序集合（基于哈希表实现） unordered_set<int> unorderedSet;大致思路：
- 用一个 unordered_set 来记录当前窗口里的字符，保证里面没有重复。
- 用 双指针 left、right 表示窗口的左右边界，left 初始为 0。
- 用 maxLen 记录遍历过程中最长的无重复子串长度。
- right 从左到右遍历字符串，每次尝试把 s [right] 加入窗口。
- 如果发现 s [right] 已经在 set 里（重复了），就 不断从左边 erase 字符、left++，直到把重复的那个字符彻底移出窗口。
- 把当前 s [right] 加入 set，更新窗口长度，维护 maxLen。
- 遍历结束后，maxLen 就是答案。
重点讲解while循环
它的作用是：当遇到重复字符时，持续移动左指针，直到移除那个重复字符。
例子：s = "abcbda"
我们用滑动窗口 [left, right] 来跟踪当前无重复字符的子串。
步骤分析：
- 初始状态：
left = 0,charSet = {} - right = 0：
'a'不在集合中，直接加入 →charSet = {'a'}, 长度=1 - right = 1：
'b'不在集合中，直接加入 →charSet = {'a', 'b'}, 长度=2 - right = 2：
'c'不在集合中，直接加入 →charSet = {'a', 'b', 'c'}, 长度=3 - right = 3：
'b'已经在集合中！- 进入
while循环 - 第一次循环：移除
s[left]（即s[0] = 'a'），left = 1 - 检查
'b'还在集合中吗？是的，因为集合现在是{'b', 'c'} - 第二次循环：移除
s[left]（即s[1] = 'b'），left = 2 - 现在集合是
{'c'}，'b'不在集合中了 - 退出
while循环 - 加入
'b'，集合变为{'c', 'b'}，长度 =right - left + 1 = 3 - 2 + 1 = 2
- 进入
- right = 4：
'd'不在集合中，直接加入 →charSet = {'c', 'b', 'd'}, 长度=3
