langShift滑动窗口（题单顺序）
热题 100 - 滑动窗口分组（按题单顺序）：3 / 438
本页包含题单「滑动窗口」分组的全部题目，顺序与 list.json 保持一致。
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 * 104s由英文字母、数字、符号和空格组成
最优解（滑动窗口 + 记录字符最近出现位置）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 朴素想法：枚举所有子串，检查是否有重复字符，取最长。子串数量是 (O(n^2))，每次检查还要扫一遍，整体会更慢。
- 瓶颈在哪里？：我们在重复做“从某个位置开始，往右扩展直到出现重复字符”的事情；很多扩展过程是重叠的。
- 关键观察（窗口的本质）：如果我们维护一个区间
[left, right]，保证这段子串里没有重复字符，那么右指针每往右走一步，我们只需要处理“新增的那一个字符”会不会造成冲突。 - 冲突怎么处理？为什么 left 不是一步步挪？
- 当
s[right] = ch在窗口里已经出现过时，窗口不再合法。 - 你真正需要的是：把
left直接跳过上一次ch出现的位置（否则窗口里仍然会有两个ch）。 - 所以我们记录
ch最近一次出现的下标lastPos[ch]，并让left = max(left, lastPos[ch] + 1)。 - 这里用
max是因为：left可能已经在更右边（比如处理过别的重复），不能往回退。
- 当
- 为什么整体是 (O(n))：
right从左到右只走一遍；left也只会向右移动且最多移动 n 次。Map 查询均摊 (O(1))。 - 用例子走一遍（抓住“跳跃”）：
"abba"- right=0 'a'：窗口 "a"，ans=1
- right=1 'b'：窗口 "ab"，ans=2
- right=2 'b'：重复，
left跳到上次 b 的位置+1 →left=2，窗口变 "b" - right=3 'a'：上次 a 在 0，不在窗口内（left=2），窗口 "ba"，ans 仍 2
- 易错点：
left只能前进不能后退，所以要写成left = Math.max(left, lastPos.get(ch) + 1)。 - 复杂度：时间 (O(n))，空间 (O(\Sigma))（字符集大小）。
类似题目（滑动窗口通用模板：右扩张 + 左收缩）
let left = 0for (let right = 0; right < n; right++) {add(arr[right]) // 把右端加入窗口while (!windowIsValid()) {remove(arr[left]) // 让窗口重新合法left++}// 此时窗口合法，可更新答案ans = update(ans, left, right)}
438. 找到字符串中所有字母异位词
给定两个字符串 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 * 104s和p仅包含小写字母
最优解（定长滑动窗口 + 计数差为 0）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：在
s里找所有起点i，使得长度为p.length的子串s[i..i+m-1]和p是异位词（字母次数完全一样）。 - 朴素做法：对每个起点都数一遍 26 个字母次数，再比较一次 → 每个窗口要 (O(26 + m))，窗口有 (O(n)) 个，整体也会偏慢。
- 关键观察：窗口长度是固定的 (m)。固定长度意味着：窗口每右移一步，只会“进来一个字符、出去一个字符”，其余字符不变。
- 怎么判断两个字符串是不是异位词？：看 26 个字母的计数是否完全相同。
- 把“相同”改写成“差为 0”：
- 我们维护
diff[26] = count(window) - count(p) - 如果
diff全部为 0，就说明窗口与p完全一致（异位词）。
- 我们维护
- 如何 (O(1)) 判断“全部为 0”？：
- 直接每次扫 26 个也可以（仍是 (O(26n))，对 26 这种常数通常够快）。
- 这里更“套路化”：维护一个
nonZero计数，表示diff[i] != 0的位置有多少个。nonZero==0就代表全为 0。 - 每次窗口移动只会影响两个字符的下标，所以
nonZero也能 (O(1)) 更新。
- 易错点：维护
nonZero时要同时处理“从 0 变非 0”和“从非 0 变 0”两种变化，否则会错判窗口是否匹配。 - 复杂度：时间 (O(n))，空间 (O(1))（固定 26 个计数）。
- 小例子走一遍：
s="abab",p="ab", m=2- 初始窗口 "ab"：diff 全 0 → 记录 0
- 窗口右移：出 'a' 进 'a'，diff 仍全 0 → 记录 1
- 再右移同理 → 记录 2
类似题目（定长窗口：进一出一维护计数/差分）
// 固定窗口长度 minitWindow(0, m - 1)for (let i = m; i < n; i++) {add(arr[i]) // 进remove(arr[i - m]) // 出if (isGood()) ans.push(i - m + 1)}