Leetcode 58 | 附：滑动窗口题单 - 教程

1 题目

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

2 代码实现

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map window;int left = 0, right = 0;// 记录结果int res = 0;while (right < s.size()) {char c = s[right];right++;// 进行窗口内数据的一系列更新window[c]++;// 判断左侧窗口是否要收缩while (window[c] > 1) {char d = s[left];left++;// 进行窗口内数据的一系列更新window[d]--;}// 在这里更新答案res = max(res, right - left);}return res;}
};

滑动窗口解题框架（cpp）

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map window;int left = 0, right = 0;// 记录结果int res = 0;while (right < s.size()) {char c = s[right];right++;// 进行窗口内数据的一系列更新window[c]++;// 判断左侧窗口是否要收缩while (window[c] > 1) {char d = s[left];left++;// 进行窗口内数据的一系列更新window[d]--;}// 在这里更新答案res = max(res, right - left);}return res;}
};

题解

1. 问题分析

题目要求找到字符串中无重复字符的最长子串长度。子串是连续的字符序列，因此需要保证窗口内的字符完全唯一，且尽可能长。

2. 滑动窗口框架适配

滑动窗口算法的核心是通过左右指针维护一个动态窗口，通过扩张和收缩窗口寻找最优解。本题中：

• 窗口含义：[left, right) 区间内的子串为当前候选的无重复子串
• 扩张策略：右指针 right 不断右移，将新字符加入窗口
• 收缩策略：当窗口中出现重复字符时，左指针 left 右移以移除重复字符
• 数据结构：用 unordered_map<char, int> 记录窗口内字符的出现次数

3. 代码逐行解析

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map window;  // 记录窗口内字符出现次数int left = 0, right = 0;          // 窗口左右边界（左闭右开）int res = 0;                      // 存储最大长度结果while (right < s.size()) {        // 右指针未越界时持续扩张窗口char c = s[right];            // 待加入窗口的字符right++;                      // 右指针右移，扩大窗口window[c]++;                  // 更新字符计数（扩张阶段的数据更新）// 当新加入的字符导致重复时，收缩左边界while (window[c] > 1) {       // 核心收缩条件：当前字符出现次数>1char d = s[left];         // 待移除窗口的字符left++;                   // 左指针右移，缩小窗口window[d]--;              // 更新字符计数（收缩阶段的数据更新）}// 此时窗口内无重复字符，计算当前窗口长度并更新最大值res = max(res, right - left);}return res;}
};

4. 关键逻辑解析

• 窗口扩张：right 从 0 移动到 s.size()-1，每次将字符 s[right] 加入窗口并更新计数
• 窗口收缩：当 window[c] > 1 时（新加入的字符 c 重复），通过移动 left 移除字符 s[left] 并减少计数，直到 window[c] == 1
• 结果更新：每次收缩完成后，窗口 [left, right) 一定是无重复子串，此时计算长度 right-left 并与历史最大值比较

5. 示例运行过程（以 "abcabcbb" 为例）

• 初始状态：left=0, right=0, res=0
• right=0：加入 'a'，窗口 [0,1)，res=1
• right=1：加入 'b'，窗口 [0,2)，res=2
• right=2：加入 'c'，窗口 [0,3)，res=3
• right=3：加入 'a'（重复），收缩 left 到 1，窗口 [1,4)，res 保持 3
• 后续过程类似，最终最大长度为 3

6. 时间与空间复杂度

• 时间复杂度：O (n)，每个字符最多被 left 和 right 指针各访问一次
• 空间复杂度：O (k)，k 为字符集大小（最多 128 个 ASCII 字符）

7. 框架对应关系

完全符合滑动窗口伪码框架：

• 用 unordered_map 实现 window 数据结构
• 扩张阶段：right++ 并更新 window[c]++
• 收缩阶段：left++ 并更新 window[d]--
• 在收缩完成后更新结果

3 滑动窗口算法经典 LeetCode 题单（按难度 + 场景分类）

基础入门（理解窗口收缩与扩张逻辑）

1. LeetCode 209. 长度最小的子数组：给定正整数数组和目标值，找和≥目标的长度最小的连续子数组，核心练 “窗口右扩找满足条件，左缩优化最小长度”。
2. LeetCode 3. 无重复字符的最长子串：找字符串中不含重复字符的最长子串，核心练 “用哈希表记录字符位置，左边界跳转到重复字符下一位”。
3. LeetCode 424. 替换后的最长重复字符：允许替换 k 个字符，找最长的重复字符子串，核心练 “窗口右扩统计最多重复字符，左缩控制替换次数≤k”。

---

中级进阶（窗口与哈希 / 计数结合）

1. LeetCode 76. 最小覆盖子串：找包含目标字符串所有字符的最短子串，核心练 “哈希表记录目标字符需求，窗口收缩时校验是否仍满足覆盖条件”。
2. LeetCode 438. 找到字符串中所有字母异位词：找字符串中所有目标串的字母异位词（字符相同顺序不同），核心练 “固定窗口长度，用计数数组比对字符频率”。
3. LeetCode 567. 字符串的排列：判断目标串的排列是否是原串的子串，核心练 “固定窗口长度 = 目标串长度，计数数组快速比对频率”。
4. LeetCode 904. 水果成篮：数组元素代表水果种类，最多选 2 种，找最长连续子数组，核心练 “用哈希表维护窗口内元素种类，左缩控制种类数≤2”。

---

高级拓展（多条件窗口 / 特殊场景）

1. LeetCode 767. 重构字符串：判断能否重排字符串使相邻字符不同，核心练 “窗口内控制同一字符最多出现一次，结合贪心思想”。
2. LeetCode 1004. 最大连续 1 的个数 III：允许翻转 k 个 0，找最长连续 1 的子数组，核心练 “窗口右扩统计 0 的个数，左缩控制 0 的个数≤k”。
3. LeetCode 1234. 替换子串得到平衡字符串：字符串由 4 种字符组成，找最短子串替换后使 4 种字符数量相等，核心练 “反向思维，窗口外字符满足数量要求时收缩”。