1. 项目概述为什么滑动窗口是子串/子数组问题的“瑞士军刀”如果你在刷LeetCode或者准备C面试尤其是面对字符串和数组相关的题目时一定对“滑动窗口”这个词不陌生。它不是什么高深莫测的黑科技而是一种极其高效、优雅的解题思想专门用来处理那些要求你找到满足特定条件的连续子串或子数组的问题。比如给你一个字符串让你找“无重复字符的最长子串”或者给你一个数组让你找“和大于等于目标值的最短子数组”。这类问题如果暴力枚举所有子串时间复杂度动辄O(n²)甚至O(n³)数据量一大直接超时。而滑动窗口算法能在O(n)的时间复杂度内优雅解决效率提升不是一点半点。我刚开始学算法时也觉得滑动窗口有点“玄学”指针移来移去容易把自己绕晕。但真正理解其核心思想并亲手用C实现过几遍后我发现它其实是这类问题最直观、最符合直觉的解法。今天我就结合自己踩过的坑和实战经验带你彻底吃透滑动窗口。我们会从最基础的固定窗口大小问题入手逐步过渡到更复杂的可变窗口并用C手把手实现几个经典例题。无论你是正在入门的数据结构与算法新手还是想巩固面试高频考点的求职者这篇内容都能让你对滑动窗口有一个系统而深刻的理解。2. 滑动窗口算法核心思想与两种模式拆解滑动窗口算法的本质是在一个线性数据结构如数组、字符串、链表上维护一个连续的、大小可变或固定的区间通过移动这个区间的左右边界来遍历所有可能的解并在这个过程中避免重复计算。你可以把它想象成用一个可伸缩的框窗口在数组或字符串上滑动。窗口的左边界left和右边界right最初都指向起始位置。然后我们通过一个主循环通常是right指针向右移动来探索整个序列。在right移动的过程中我们不断更新窗口内的状态比如字符出现次数、元素和等。当窗口内的状态满足某个条件时比如包含了目标子串的所有字符或者和超过了阈值我们就开始尝试移动left指针来收缩窗口以寻找更优解或使窗口重新满足条件。根据窗口大小是否固定滑动窗口主要分为两种模式理解这两种模式是掌握该算法的关键。2.1 模式一固定大小的窗口这种模式最简单。窗口的大小k是预先给定的。我们只需要初始化一个包含前k个元素的窗口计算其初始状态如和、最大值等然后每次将窗口向右滑动一格移除最左边的元素加入右边的新元素并更新窗口状态。核心操作步骤初始化计算数组/字符串前k个元素的状态作为第一个窗口。滑动从第k个元素开始用循环变量i遍历。移除窗口离开的元素arr[i-k]。加入窗口新进入的元素arr[i]。更新窗口状态如和、最大值队列等。根据题目要求记录或比较当前窗口的状态例如记录最大和或最小和。C实现示例计算大小为k的子数组的最大和#include vector #include algorithm #include climits using namespace std; int maxSumFixedWindow(vectorint nums, int k) { if (nums.size() k) return -1; // 处理边界 int windowSum 0; // 计算初始窗口和 for (int i 0; i k; i) { windowSum nums[i]; } int maxSum windowSum; // 开始滑动窗口 for (int i k; i nums.size(); i) { windowSum windowSum - nums[i - k] nums[i]; // 滑动去旧加新 maxSum max(maxSum, windowSum); } return maxSum; }注意固定窗口问题有时会伪装成其他形式比如“给定字符串找到所有长度为k的异位词”。其本质依然是窗口大小固定只是判断条件从“和”变成了“字符计数是否匹配”。2.2 模式二可变大小的窗口双指针型这是滑动窗口的精华和难点所在。窗口的大小不再固定而是根据题目条件动态调整。通常我们使用两个指针left和right来标识窗口的左右边界并维护一个数据结构如哈希表unordered_map来记录窗口内的状态。通用算法框架模板int left 0, right 0; // 初始化窗口边界 unordered_mapchar, int window; // 用于记录窗口内状态的哈希表 int valid 0; // 用于记录窗口中满足某个条件的元素个数 while (right s.size()) { // c 是将移入窗口的字符 char c s[right]; // 右移窗口 right; // 进行窗口内数据的一系列更新 // ... (更新window, valid等) /*** debug 输出的位置 ***/ printf(window: [%d, %d)\n, left, right); /********************/ // 判断左侧窗口是否要收缩 while (window needs shrink) { // d 是将移出窗口的字符 char d s[left]; // 左移窗口 left; // 进行窗口内数据的一系列更新 // ... (更新window, valid等) } // 在这里更新答案可能在收缩窗口前也可能在后视题目而定 }这个框架几乎能解决所有可变窗口的字符串/数组问题。你需要根据具体问题填充“数据更新”和“收缩条件”的逻辑。两种常见的收缩条件寻找最小窗口当窗口满足条件时我们尝试收缩left指针以找到更小的满足条件的窗口并在此过程中更新答案。例如“最小覆盖子串”。寻找最大窗口当窗口不满足条件时我们收缩left指针直到窗口重新满足条件然后尝试继续扩展right。例如“无重复字符的最长子串”。3. 核心细节解析与C实现要点理解了两种模式我们还需要深入一些实现细节这些细节决定了代码的正确性和效率。3.1 状态维护哈希表unordered_map的正确使用在可变窗口问题中我们经常需要快速查询、增加、减少窗口中某个字符或数字的出现次数。C的std::unordered_map基于哈希表是绝佳选择它提供O(1)时间复杂度的查找、插入和删除平均情况。关键操作window[c]: 当right指针右移字符c进入窗口。window[d]--: 当left指针右移字符d离开窗口。这里有一个巨坑当某个字符的计数减到0时为了后续判断方便最好将其从unordered_map中erase掉。因为判断window.count(d)或window[d] 0比判断window[d] 0更清晰且能避免window中堆积大量计数为0的键值对。if (--window[d] 0) { window.erase(d); // 重要清理计数为0的项 }3.2 条件判断valid变量的妙用如何高效判断当前窗口是否满足了题目的要求例如是否包含了目标字符串t的所有字符一个高效的方法是引入valid变量。我们通常需要两个哈希表need记录目标t中每个字符需要的数量window记录当前窗口中各字符的数量。valid表示当前窗口中有多少种字符的数量已经达到了need要求。当window[c]增加后等于need[c]时valid。当window[d]减少后小于need[d]时valid--。当valid need.size()时说明窗口已经覆盖了t的所有字符。这种方法避免了每次收缩时都遍历比较两个哈希表将O(n)的比较降为O(1)的整数比较。3.3 边界处理与循环不变式编写滑动窗口代码时时刻明确循环不变式至关重要。通常我们约定窗口是左闭右开区间[left, right)。这意味着right指向的是即将加入窗口的元素或者当前窗口的右边界不包含。left指向的是窗口的左边界包含。初始时left right 0窗口[0, 0)为空。当right指针递增后窗口向右扩大。当left指针递增后窗口向左收缩。保持这个约定能让你的逻辑清晰避免出现差一错误off-by-one error。4. 经典例题实战从原理到C代码光说不练假把式。下面我们用三个经典LeetCode例题带你完整走一遍分析、实现和调试的过程。4.1 例题一无重复字符的最长子串LeetCode 3问题给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。分析这是典型的“可变窗口-寻找最大窗口”问题。我们需要一个窗口窗口内的所有字符都是唯一的。当right指针向右移动遇到一个重复字符时窗口就不满足条件了此时需要移动left指针直到将那个重复字符移出窗口。C实现与逐行解析#include string #include unordered_set using namespace std; int lengthOfLongestSubstring(string s) { unordered_setchar window; // 使用集合存储窗口内字符保证唯一性 int left 0, right 0; int maxLen 0; int n s.size(); while (right n) { char c s[right]; // 如果当前字符不在窗口中直接加入 if (window.find(c) window.end()) { window.insert(c); right; // 更新最大长度窗口大小为 right - left maxLen max(maxLen, right - left); } else { // 如果字符已存在需要收缩左边界直到移除这个重复字符 char d s[left]; window.erase(d); left; } } return maxLen; }优化点上述代码在遇到重复字符时left一次只移动一位在最坏情况如”aaaaa”下是O(n²)。我们可以用哈希表记录字符最后一次出现的位置让left直接跳到重复字符的下一位。int lengthOfLongestSubstringOpt(string s) { unordered_mapchar, int charIndex; // 记录字符最近一次出现的下标 int left 0, maxLen 0; for (int right 0; right s.size(); right) { char c s[right]; // 如果字符出现过并且在当前窗口内下标left则快速收缩left if (charIndex.find(c) ! charIndex.end() charIndex[c] left) { left charIndex[c] 1; // 直接跳到重复字符的下一位 } charIndex[c] right; // 更新字符最新位置 maxLen max(maxLen, right - left 1); // 当前窗口长度是 right-left1 } return maxLen; }实操心得unordered_map的[]运算符会在键不存在时自动插入这在这里很方便。但要注意charIndex[c] left这个判断是关键它确保了被跳过的重复字符确实在当前窗口内而不是历史上出现过但已不在窗口中的字符。4.2 例题二最小覆盖子串LeetCode 76问题给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果不存在则返回空字符串。分析这是“可变窗口-寻找最小窗口”的终极BOSS题。我们需要在s中找到一个窗口该窗口包含t的所有字符包括数量并且要求这个窗口长度最小。C实现详解#include string #include unordered_map using namespace std; string minWindow(string s, string t) { unordered_mapchar, int need, window; // 初始化need哈希表记录t中每个字符需要的数量 for (char c : t) need[c]; int left 0, right 0; int valid 0; // 窗口中满足need条件的字符种类数 // 记录最小覆盖子串的起始索引和长度 int start 0, len INT_MAX; while (right s.size()) { // c 是将移入窗口的字符 char c s[right]; // 右移窗口 right; // 进行窗口内数据的一系列更新 if (need.count(c)) { // 只关心在need中的字符 window[c]; if (window[c] need[c]) { valid; // 该字符数量已满足要求 } } // 判断左侧窗口是否要收缩 // 当窗口已覆盖t的所有字符时尝试收缩找更小的窗口 while (valid need.size()) { // 更新最小覆盖子串 if (right - left len) { start left; len right - left; } // d 是将移出窗口的字符 char d s[left]; // 左移窗口 left; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] need[d]) { valid--; // 该字符即将不满足要求 } window[d]--; // 可选清理if(window[d]0) window.erase(d); } } } // 返回结果 return len INT_MAX ? : s.substr(start, len); }关键点解析need和windowneed是目标window是现状。我们只关心出现在need里的字符。valid的作用它是我们判断窗口是否“已覆盖”t的快速通道。避免了每次比较两个完整的哈希表。收缩时机while (valid need.size())是核心。一旦覆盖就不断收缩left直到刚好不覆盖为止。每次收缩前都记录一下当前窗口从而找到全局最小窗口。更新答案的位置在收缩窗口的while循环内部更新start和len。因为此时窗口是满足条件的我们要在它被破坏前记录下它的状态。4.3 例题三字符串的排列LeetCode 567问题给你两个字符串s1和s2判断s2是否包含s1的排列。分析这可以看作是“固定窗口”问题的一个变种但窗口大小固定为s1.length()。我们需要在s2上滑动这个固定大小的窗口检查窗口内的字符及其数量是否与s1完全一致。也可以看作“最小覆盖子串”的简化版要求窗口大小固定且必须完全匹配。C实现固定窗口哈希表法bool checkInclusion(string s1, string s2) { int n1 s1.size(), n2 s2.size(); if (n1 n2) return false; vectorint count1(26, 0), count2(26, 0); // 因为只有小写字母用数组比哈希表更快 // 初始化第一个窗口和s1的计数 for (int i 0; i n1; i) { count1[s1[i] - a]; count2[s2[i] - a]; } // 如果第一个窗口就匹配直接返回true if (count1 count2) return true; // 开始滑动窗口 for (int i n1; i n2; i) { // 窗口右移移除左边字符加入右边字符 count2[s2[i - n1] - a]--; // 移除窗口最左边的字符 count2[s2[i] - a]; // 加入新进入窗口的字符 // 比较两个计数数组是否相等 if (count1 count2) return true; } return false; }优化思路双指针可变窗口法我们也可以将其视为一个可变窗口问题在s2中寻找一个窗口使得窗口内字符计数与s1的计数完全一致且窗口长度等于s1.length()。这相当于在s2上维护一个窗口当窗口长度等于n1时检查是否匹配如果某个字符导致窗口内该字符数量超过s1中的数量则收缩左边界。bool checkInclusionSlidingWindow(string s1, string s2) { unordered_mapchar, int need, window; for (char c : s1) need[c]; int left 0, right 0; int valid 0; while (right s2.size()) { char c s2[right]; right; if (need.count(c)) { window[c]; if (window[c] need[c]) valid; } // 当窗口大小大于等于s1长度时需要收缩 while (right - left s1.size()) { // 如果窗口大小等于s1长度且所有字符都匹配则找到排列 if (valid need.size() (right - left) s1.size()) { return true; } char d s2[left]; left; if (need.count(d)) { if (window[d] need[d]) valid--; window[d]--; } } } return false; }注意事项对于字符集有限如只有小写字母的情况使用vectorint(26,0)作为计数器通常比unordered_map更快因为数组的访问是O(1)且常数因子更小。但在字符集较大或不确定时哈希表更通用。在面试中可以先提一下数组优化的可能性展示你的思考深度。5. 滑动窗口的变体、优化与常见陷阱掌握了基本框架和经典例题我们还需要了解一些高级变体和常见错误这样才能在实战中游刃有余。5.1 涉及数值和的滑动窗口问题当问题涉及子数组的和例如求和大于等于target的最短子数组时窗口状态通常是一个简单的整数sum。这类问题看似简单但收缩条件需要仔细斟酌。例题长度最小的子数组LeetCode 209int minSubArrayLen(int target, vectorint nums) { int left 0, sum 0; int 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; }陷阱这里的收缩条件是while (sum target)而不是if。因为可能收缩一次后sum仍然大于等于target此时窗口可以继续收缩以找到更短的子数组。如果用if就只能找到第一个满足条件的窗口不一定是长度最小的。5.2 使用双端队列deque维护窗口最值有一类特殊问题需要在滑动窗口过程中快速获取窗口内的最大值或最小值。例如“滑动窗口最大值”LeetCode 239。此时简单的变量或哈希表无法满足要求我们需要一个能在两端高效操作的数据结构——双端队列deque。核心思想维护一个单调递减队列队头始终是当前窗口最大值。队列中存储的是元素的索引而不是值这是为了便于判断队头元素是否还在当前窗口内。当窗口滑动时移除队尾所有小于新元素的索引保持递减性。将新元素索引加入队尾。检查队头索引是否已滑出窗口若是则弹出队头。当窗口形成后right k-1队头索引对应的值就是当前窗口的最大值。C实现vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存储索引对应值单调递减 vectorint res; for (int right 0; right nums.size(); right) { // 维护单调性移除队尾所有小于新元素的索引 while (!dq.empty() nums[dq.back()] nums[right]) { dq.pop_back(); } dq.push_back(right); // 移除滑出窗口的队头元素 if (dq.front() right - k 1) { dq.pop_front(); } // 当窗口形成时记录结果 if (right k - 1) { res.push_back(nums[dq.front()]); } } return res; }实操心得deque的push_back、pop_back、pop_front都是O(1)操作。整个算法每个元素最多入队出队各一次因此总时间复杂度是O(n)。这是利用数据结构特性对滑动窗口进行优化的典范。5.3 常见陷阱与调试技巧指针移动与状态更新的顺序这是最容易出错的地方。务必想清楚是先移动指针再更新状态还是先更新状态再移动指针这取决于你对窗口区间的定义左闭右开[left, right)还是左闭右闭[left, right]。一旦确定一种约定整个代码逻辑必须保持一致。我强烈推荐使用[left, right)约定它能让“窗口大小”等于right - left非常直观。收缩条件的循环与判断收缩窗口时使用while循环而不是if判断除非你确定只需要收缩一次。很多题目如求最小窗口需要不断收缩直到条件不再满足。哈希表键的清理如前所述当window中某个字符计数减到0时考虑将其erase掉。这能让window.size()反映窗口内不同字符的数量有时可以简化判断逻辑。调试输出在复杂的问题中可以在循环内打印left、right、window和valid的值这是理解窗口如何滑动的绝佳方式。// 在窗口更新后打印 printf(l%d, r%d, valid%d, window: , left, right, valid); for (auto p : window) if(p.second0) cout p.first : p.second ; cout endl;空串和边界处理总是先考虑输入为空、目标字符串比源字符串长等边界情况并在代码开头进行处理避免核心逻辑出现未定义行为。6. 滑动窗口算法的时间复杂度与空间复杂度分析正确分析复杂度是算法能力的体现也是面试中的必问题。时间复杂度O(n)这是滑动窗口算法最吸引人的地方。虽然代码中有嵌套的while循环但请你仔细观察left和right指针都只从0移动到n字符串/数组长度且每个元素最多被left和right各访问一次。因此所有操作的总次数与n成线性关系时间复杂度是O(n)。嵌套循环并不意味着O(n²)这里的while循环是“摊还”意义上的O(1)操作。空间复杂度O(k) 或 O(字符集大小)空间开销主要来自用于记录状态的哈希表或数组。对于固定字符集如小写字母的问题使用数组vectorint(26,0)空间复杂度是O(1)因为数组大小固定。对于通用字符或整数问题使用unordered_map在最坏情况下所有字符都不同需要存储O(n)个键值对。但通常我们更关注窗口内不同元素的数量如果窗口大小受限制或字符集有限可以认为是O(k)其中k是窗口大小的上限。7. 如何识别一个问题是否能用滑动窗口解决不是所有子串/子数组问题都适用滑动窗口。我总结了一个快速判断的 checklist问题是否涉及“连续子序列”滑动窗口只适用于连续的区间。求解目标是否与区间内的“状态”有关例如求最大/最小长度、判断是否存在满足某条件的区间、统计满足条件的区间个数等。当窗口右边界向右移动时窗口内的状态更新是否容易计算例如增加一个字符的计数。当窗口左边界向右移动时能否高效地撤销之前的状态更新例如减少一个字符的计数。如果以上问题的答案都是“是”那么滑动窗口就很可能是一个高效的解法。典型特征包括题目描述中出现“最小覆盖子串”、“最长无重复子串”、“找到所有字母异位词”、“和为K的连续子数组”等。最后再分享一个我自己的练习方法找一张纸手动模拟left和right指针的移动以及window和valid的变化。这个过程能极大地加深你对算法“肌肉记忆”的理解。滑动窗口的代码看似有套路但细微的逻辑差别会导致完全不同的结果。多写、多调、多模拟你就能把它从“知道”变成“精通”在面试和实战中稳稳地拿下这一类题目。