一、3. 无重复字符的最长子串 题目链接LeetCode 3. 无重复字符的最长子串 题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。示例输入s abcabcbb 输出3 解释无重复字符的最长子串是 abc长度为 3。 输入s bbbbb 输出1 解释最长子串是 b长度为 1。 输入s pwwkew 输出3 解释最长子串是 wke 或 kew长度为 3。 思路分析滑动窗口的核心思想是维护一个动态区间保证窗口内始终没有重复字符。用两个指针left和right来表示窗口的左右边界right指针不断向右扩展将新字符纳入窗口。如果发现新字符已经在窗口中出现过就移动left指针向右收缩直到把那个重复的字符踢出窗口。每次扩展后窗口长度right - left 1就是当前无重复子串的长度用全局变量记录这个长度的最大值。整个过程只需要遍历一次字符串时间复杂度 O(n)。判断字符是否在窗口内可以用哈希表或数组记录每个字符最新出现的位置这样就能快速定位到left应该跳到哪里。 代码实现Cclass Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int lastPos; int left 0, maxLen 0; for (int right 0; right s.size(); right) { char c s[right]; if (lastPos.find(c) ! lastPos.end() lastPos[c] left) { left lastPos[c] 1; } lastPos[c] right; maxLen max(maxLen, right - left 1); } return maxLen; } }; 相关学习资源视频Leetcode力扣3-无重复字符的最长子串滑动窗口双指针文章无重复字符的最长子串从直觉到最优解免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(n)每个字符被访问一次。空间复杂度O(∣Σ∣)Σ 是字符集大小通常为 128 或 256。二、438. 找到字符串中所有字母异位词 题目链接LeetCode 438. 找到字符串中所有字母异位词 题目描述给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。异位词指由相同字母重排列形成的字符串包括相同的字符串。示例输入s cbaebabacd, p abc 输出[0,6] 解释起始索引 0 的子串是 cba它是 abc 的异位词起始索引 6 的子串是 bac它也是 abc 的异位词。 思路分析这道题的关键在于两点第一异位词的长度和模式串p的长度相同所以窗口大小是固定的第二判断两个字符串是否互为异位词只需要比较它们包含的字符种类和每种字符的数量是否一致。具体做法是先用一个频次数组统计p中每个字符的出现次数然后在s中维护一个长度等于p.size()的滑动窗口同时维护当前窗口的频次数组。窗口每次向右滑动一步右边加入一个新字符频次加 1左边移除一个旧字符频次减 1。每次滑动后比较当前窗口的频次数组和p的频次数组是否相同如果相同就把窗口的左边界加入结果集。由于题目限定了字符串只包含小写字母用vectorint(26, 0)代替哈希表可以极大提升性能C 中vector重载了运算符可以直接比较两个频次数组是否相等。 代码实现Cclass Solution { public: vectorint findAnagrams(string s, string p) { vectorint res; int m s.size(), n p.size(); if (m n) return res; vectorint p_cnt(26, 0), win_cnt(26, 0); for (int i 0; i n; i) { p_cnt[p[i] - a]; win_cnt[s[i] - a]; } if (p_cnt win_cnt) res.push_back(0); for (int i n; i m; i) { win_cnt[s[i] - a]; win_cnt[s[i - n] - a]--; if (p_cnt win_cnt) res.push_back(i - n 1); } return res; } }; 相关学习资源视频所有字母异位词怎么找一个动画讲懂固定窗口频次比较文章LeetCode 438. 找到字符串中所有字母异位词 | C 滑动窗口题解免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(n)其中 n 是字符串s的长度。空间复杂度O(1)频次数组大小固定为 26。三、76. 最小覆盖子串 题目链接LeetCode 76. 最小覆盖子串 题目描述给你一个字符串s和字符串t请在s中找出包含t所有字符的最短子串。如果不存在这样的子串返回空字符串。示例输入s ADOBECODEBANC, t ABC 输出BANC 解释最小覆盖子串 BANC 包含了来自 t 的 A、B 和 C。 思路分析这道题是滑动窗口中最经典也是最难的一道。核心思路是“先扩后缩”两步走先用right指针向右扩展直到窗口内包含了t中所有字符找到一个可行解然后用left指针向右收缩尽可能缩短窗口长度直到窗口不再满足条件。在这个过程中不断记录最短子串的起始位置和长度。实现上需要两个哈希表need记录t中每个字符需要的数量windows记录当前窗口中对应字符的数量还有一个变量valid记录当前窗口中已经满足数量要求的字符种类数。当valid need.size()时说明窗口已经覆盖了t的所有字符。这个解法的时间复杂度是 O(n)因为每个字符最多被加入和移出窗口各一次。 代码实现Cclass Solution { public: string minWindow(string s, string t) { unordered_mapchar, int need, windows; for (char c : t) need[c]; int left 0, right 0, valid 0; int start 0, minLen INT_MAX; while (right s.size()) { char c s[right]; right; if (need.count(c)) { windows[c]; if (windows[c] need[c]) valid; } while (valid need.size()) { if (right - left minLen) { start left; minLen right - left; } char d s[left]; left; if (need.count(d)) { if (windows[d] need[d]) valid--; windows[d]--; } } } return minLen INT_MAX ? : s.substr(start, minLen); } }; 相关学习资源视频最小覆盖子串怎么想到先扩后缩一个动画讲懂变长窗口计数模型文章LeetCode 76. 最小覆盖子串 | C 滑动窗口题解免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(n)左右指针各移动一次。空间复杂度O(∣Σ∣)Σ 是字符集大小。四、239. 滑动窗口最大值 题目链接LeetCode 239. 滑动窗口最大值 题目描述给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位返回每个窗口中的最大值。示例输入nums [1,3,-1,-3,5,3,6,7], k 3 输出[3,3,5,5,6,7] 解释窗口位置 → 最大值 [1 3 -1] -3 5 3 6 7 → 3 1 [3 -1 -3] 5 3 6 7 → 3 1 3 [-1 -3 5] 3 6 7 → 5 1 3 -1 [-3 5 3] 6 7 → 5 1 3 -1 -3 [5 3 6] 7 → 6 1 3 -1 -3 5 [3 6 7] → 7 思路分析这道题的难点在于如何快速找到窗口内的最大值。暴力解法每次遍历窗口中的 k 个元素时间复杂度 O(nk)在大数据量下效率极低。最优秀的解法是使用单调队列用一个双端队列deque维护窗口中元素的下标保证队列中的下标对应的元素值是单调递减的从队头到队尾。窗口移动时右边新加入一个元素如果它比队尾的元素大就把队尾元素弹出直到队列重新满足单调递减左边如果有一个元素已经滑出了窗口就检查队头是否对应这个过期元素如果是就把它从队头弹出。这样一来队头永远指向当前窗口的最大值。每个元素最多入队出队各一次时间复杂度 O(n)。 代码实现Cclass Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint res; dequeint dq; for (int i 0; i nums.size(); i) { while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); if (dq.front() i - k) { dq.pop_front(); } if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; } }; 相关学习资源视频单调队列正式登场LeetCode239. 滑动窗口最大值文章LeetCode 239. 滑动窗口最大值 | C 优先队列与单调队列双解法免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(n)每个元素最多入队和出队一次。空间复杂度O(k)双端队列最多存储 k 个元素。结语滑动窗口的四道题难度逐渐递增基本覆盖了这类题的所有套路变长窗口无重复字符的最长子串、定长窗口找到所有字母异位词、最小覆盖子串先扩后缩的经典模式、单调队列维护窗口最值。其中 76 和 239 是滑动窗口中的天花板级题目吃透这两道题再遇到类似的子串/子数组问题基本都能迎刃而解。建议刷题顺序先做 3 和 438 熟悉滑动窗口的基本操作再做 76 理解“先扩后缩”的精髓最后用 239 收尾掌握单调队列的高阶技巧。下一篇将进入动态规划进阶篇敬请期待。如果本文对你有帮助欢迎点赞、收藏、转发你的支持是我持续创作的动力 ❤️免责声明本文部分解题思路参考了力扣官方题解及社区优秀文章相关链接均来自公开网络。若存在侵权问题请联系删除。