langShift子串（题单顺序）
热题 100 - 子串分组（按题单顺序）：560 / 239 / 76
本页包含题单「子串」分组的全部题目，顺序与 list.json 保持一致。
560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
最优解（前缀和 + 哈希表：把“求区间和”改成“找差值”）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 先写出区间和的公式：设
prefix[i]表示前 i 个数的和（从 0 开始），那么子数组nums[l..r]的和是：sum(l..r) = prefix[r+1] - prefix[l]
- 题目要的是
sum(l..r) = k，把上式改写：prefix[r+1] - prefix[l] = kprefix[l] = prefix[r+1] - k
- 这一步很关键：把“找一段区间”变成“找一个历史前缀值”。
- 当我们遍历到
r（也就是当前前缀和prefix），想知道有多少个l能让区间和为k， - 只需要问：以前出现过多少次
prefix - k？
- 当我们遍历到
- 为什么要存“次数”而不是“下标”？
- 因为可能有多个
l让prefix[l]相同（例如有 0、正负抵消），每一个都对应一个合法子数组。 - 所以
Map里存的是前缀和 -> 出现次数。
- 因为可能有多个
- 为什么初始要
countByPrefix.set(0,1)？- 表示“在任何元素之前，前缀和为 0 出现过一次”。
- 这样当某个前缀和本身就等于 k 时（即从 0 开始到当前位置的子数组），也能正确统计到。
- 小例子走一遍：
nums=[1,1,1],k=2- 初始：count[0]=1
- 扫到第 2 个 1（prefix=2）时，need=0，count[0]=1 → ans+=1（子数组 [1,1]）
- 扫到第 3 个 1（prefix=3）时，need=1，count[1]=1 → ans+=1（子数组 [1,1] 从第二个开始）
- 为什么不是滑动窗口？：因为数组里可能有负数，窗口右移/左移时区间和不具备单调性，滑动窗口会失效；前缀和 + 哈希才是通用解。
- 复杂度：时间 (O(n))，空间 (O(n))（最坏情况下前缀和都不同）。
类似题目（前缀和 + 哈希：统计满足差值的区间）
const freq = new Map()freq.set(0, 1)let prefix = 0let ans = 0for (const x of nums) {prefix += x// 关键：把“区间条件”改写成“前缀差值条件”ans += freq.get(prefix - target) || 0freq.set(prefix, (freq.get(prefix) || 0) + 1)}
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：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
示例 2：
输入：nums = [1], k = 1 输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
最优解（单调队列：队头永远是最大值）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：窗口长度固定为
k，每向右滑一步，就输出当前窗口里的最大值。 - 朴素做法：每个窗口都扫一遍找最大值，单个窗口 (O(k))，总共 (O(nk))，k 大就超时。
- 关键观察：窗口滑动时，只进一个元素、出一个元素。我们想维护一个数据结构，让“取最大值”是 (O(1))。
- 为什么用“单调队列”？
- 我们维护一个队列，里面存的是“可能成为当前/未来窗口最大值”的候选下标。
- 队列对应的值必须从头到尾递减：这样队头永远是最大值。
- 推理队列规则（最容易写对的部分）：
- 新元素进来时：把队尾所有
<= 新元素的都弹掉- 因为新元素更大（或相等且更新），而且更靠右、活得更久；那些更小的再也不可能成为最大值。
- 窗口右移时：如果队头下标已经滑出窗口（
<= i-k），就把它弹掉。 - 窗口形成后：直接取
nums[dq[0]]作为最大值。
- 新元素进来时：把队尾所有
- 为什么是 (O(n))：每个元素最多进队一次、出队一次，所有
pop/shift总次数是线性的。 - 复杂度：时间 (O(n))，空间 (O(k))（队列最多保留一个窗口内的候选下标）。
类似题目（单调队列模板：维护“最值”）
const dq = [] // 存下标，保证单调for (let i = 0; i < n; i++) {while (dq.length && worse(dq[dq.length - 1], i)) dq.pop()dq.push(i)if (dq[0] <= i - k) dq.shift()if (i >= k - 1) ans.push(value(dq[0]))}
76. 最小覆盖子串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在
O(m + n) 时间内解决此问题的算法吗？最优解（滑动窗口：先扩张满足，再收缩到最短）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：在
s中找一个最短子串，要求它包含t的所有字符（包含次数也要满足，比如t="AABC"就需要 2 个 A）。 - 为什么不能暴力？：枚举所有子串是 (O(n^2))，每个子串再检查是否覆盖 t，又会更慢。
- 滑动窗口的适用前提：我们要找的是“满足条件的最短窗口”，这类题通常都能用：
- 右指针负责“让窗口满足条件”
- 一旦满足条件，左指针就尽量“压缩”窗口
- 怎么判定“窗口是否已经覆盖 t”？
- 用
need记录每个字符还差多少个（可以为负，表示窗口里多出来了）。 - 用
missing记录还缺多少个字符（总缺口）：当missing == 0，说明覆盖成功。
- 用
- 为什么
need可以变成负数？- 负数代表“这个字符窗口里多了”，多了并不影响覆盖，只影响我们能否把左边界往右缩。
- 正数才代表“还缺”，一旦某个字符从 0 变回 1，说明窗口不再覆盖。
- 推理窗口过程：
right右移：每看到一个t里需要的字符，就把need[ch]--；如果它原本还缺（need[ch] > 0），则missing--。- 当
missing == 0：窗口已经“够用了”，此时再扩大只会更长，所以开始移动left尝试缩短。 left右移时如果移走了一个关键字符（导致need[out] > 0），说明窗口不够了，停止收缩，回到步骤 1 继续扩张。
- 小例子抓住直觉：
s="ADOBECODEBANC", t="ABC"- 先扩到第一次覆盖（包含 A/B/C），然后开始收缩左边，缩到刚好不能再缩为止；
- 再继续往右扩，找到新的覆盖，再收缩……不断更新最短答案，最终得到 "BANC"。
- 易错点：
missing只在“确实补上了缺口”时才--；移出字符后只有在need[out] > 0（变回缺口）时才++。need允许为负数是正常的，它表示“窗口里多出来的字符”，不应当触发missing变化。
- 复杂度：左右指针都只单调前进，整体时间 (O(n))，空间 (O(|\Sigma|))（字符表大小，常见场景可视为常数）。
类似题目（可变长窗口：先满足再极限收缩）
let left = 0for (let right = 0; right < n; right++) {add(arr[right])while (windowIsValid()) {ans = update(ans, left, right) // 在“合法”状态下更新最短/最优remove(arr[left])left++}}