LeetCode Hot 100 | 滑动窗口专题（C++ 题解）

LeetCode Hot 100 | 滑动窗口专题C 题解滑动窗口是处理连续子数组/子字符串问题的核心技巧通过维护一个可变窗口来避免重复计算将 O(n²) 的暴力枚举优化到 O(n)。本文涵盖 LeetCode Hot 100 中 2 道经典滑动窗口题目配有图解和详细思路分析。目录LeetCode Hot 100 | 滑动窗口专题C 题解一、3. Longest Substring Without Repeating Characters无重复字符的最长子串 中等题目描述图解解题思路C 代码二、438. Find All Anagrams in a String找到字符串中所有字母异位词 中等题目描述图解解题思路C 代码总结一、3. Longest Substring Without Repeating Characters无重复字符的最长子串 中等题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。示例 1输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2输入: s bbbbb 输出: 1 解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3输入: s pwwkew 输出: 3 解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 注意你的答案必须是子串的长度pwke 是一个子序列不是子串。提示0 s.length 5 * 10^4s由英文字母、数字、符号和空格组成图解解题思路暴力思路枚举所有子串s[i..j]对每个子串检查是否有重复字符。双重循环枚举端点 O(n²)判断重复 O(n)总体 O(n³)显然超时。滑动窗口优化用left和right两个指针维护窗口[left, right]保证窗口内始终无重复字符。right不断右移扩展窗口当遇到重复字符时left右跳到重复字符上一次出现位置的下一个消除重复。用unordered_map记录窗口内每个字符最后出现的下标实现 O(1) 判断与跳转。当right移到字符c若map[c]存在且map[c] left说明c在当前窗口内left跳到map[c] 1否则直接扩展更新ans max(ans, right - left 1)关键细节left直接跳到map[c] 1而不是逐步右移——这是 O(n) 而不是 O(n²) 的核心所在。举例走一遍s abcabcbbright0a无重复窗口[0,0]ans1right1b无重复窗口[0,1]ans2right2c无重复窗口[0,2]ans3right3amap[a]0 ≥ left0left 跳到 1窗口[1,3]ans3right4bmap[b]1 ≥ left1left 跳到 2窗口[2,4]ans3right5cmap[c]2 ≥ left2left 跳到 3窗口[3,5]ans3right6bmap[b]4 ≥ left3left 跳到 5窗口[5,6]ans3right7bmap[b]6 ≥ left5left 跳到 7窗口[7,7]ans3最终 ans3正确整个过程right走了 8 步left最多也只走了 8 步每个字符最多访问两次O(n)。复杂度时间 O(n)空间 O(|Σ|)字符集大小最多 128C 代码classSolution{public:intlengthOfLongestSubstring(string s){unordered_mapint,intumap;intleft0;intans0;for(intright0;rights.size();right){umap[s[right]];while(umap[s[right]]1){umap[s[left]]--;left;}ansmax(ans,right-left1);}returnans;}};二、438. Find All Anagrams in a String找到字符串中所有字母异位词 中等题目描述给定两个字符串s和p找到s中所有p的字母异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。字母异位词指由相同字母重排列形成的字符串包括相同的字符串。示例 1输入: s cbaebabacd, p abc 输出: [0,6] 解释: 起始索引等于 0 的子串是 cba, 它是 abc 的字母异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的字母异位词。示例 2输入: s abab, p ab 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 ab, 它是 ab 的字母异位词。 起始索引等于 1 的子串是 ba, 它是 ab 的字母异位词。 起始索引等于 2 的子串是 ab, 它是 ab 的字母异位词。提示1 s.length, p.length 3 * 10^4s和p仅包含小写英文字母图解解题思路暴力思路枚举s中每个长度为len(p)的子串排序后与排序后的p比较。O(n·k log k)k len§当 n 和 k 都很大时很慢。固定窗口滑动和第 3 题的可变窗口不同这道题的窗口大小是固定的恰好等于p.length()。窗口从左向右滑动每次移入右侧一个新字符、移出左侧一个旧字符用字符频率数组判断当前窗口是否是p的字母异位词。如何快速判断「当前窗口 p 的字母异位词」维护两个频率数组cnt_p[26]p 的字符频率预处理一次和cnt_w[26]当前窗口的字符频率随滑动动态维护。每次滑动只更新一进一出两个字符O(1) 完成更新。判断相等时直接比较两个数组O(26) O(1)。进一步优化用差值计数代替数组比较。维护diff表示当前窗口与p有多少个字符的频率不同diff 0时即为异位词。每次滑动时移入新字符c_in若更新后cnt_w[c_in] cnt_p[c_in]diff–否则若更新前相等则 diff移出旧字符c_out同理这样每次滑动只需 O(1) 判断整体 O(n)。举例走一遍s cbaebabacd, p abclen3窗口[0,2] “cba”cnt_w{a:1,b:1,c:1} cnt_pdiff0✅ 记录 0窗口[1,3] “bae”移入 ‘e’移出 ‘c’diff≠0跳过窗口[2,4] “aeb”diff≠0跳过窗口[3,5] “eba”diff≠0跳过窗口[4,6] “bab”diff≠0跳过窗口[5,7] “aba”diff≠0跳过窗口[6,8] “bac”cnt_w{a:1,b:1,c:1} cnt_pdiff0✅ 记录 6窗口[7,9] “acd”diff≠0跳过结果 [0, 6]正确复杂度时间 O(n)空间 O(|Σ|) O(26)C 代码classSolution{public:vectorintfindAnagrams(string s,string p){arrayint,26cnt;vectorintans;for(autoc:p)cnt[c-a];intleft0;for(intright0;rights.size();right){cnt[s[right]-a]--;while(cnt[s[right]-a]0){cnt[s[left]-a];left;}if(right-left1p.size())ans.push_back(left);}returnans;}};总结题号题目难度窗口类型时间复杂度3无重复字符的最长子串 中等可变窗口 哈希表跳跃O(n)438找到字符串中所有字母异位词 中等固定窗口 频率差值计数O(n)滑动窗口的本质利用问题的单调性让左右指针各自只向右移动保证每个元素最多进出窗口一次从而将枚举所有子串的 O(n²) 降到 O(n)。可变窗口靠条件驱动 left 右移固定窗口则每步严格一进一出。如果这篇文章对你有帮助欢迎点赞收藏 ⭐也欢迎在评论区交流