子串与子数组问题概述
子串（字符串连续片段）与子数组（数组连续片段）在算法题中占据半壁江山。解决此类问题的优化思路通常围绕"消除重复计算"展开，常见工具包括：
- 前缀和 + 哈希表：将区间和转化为两前缀和之差，O(1) 查询目标值，典型题如和为 K 的子数组。
- 单调队列：维护窗口内的极值，在滑动过程中 O(1) 获取最大值/最小值，典型题如滑动窗口最大值。
- 双指针滑动窗口：动态伸缩窗口，配合状态变量（频次计数）在 O(n) 内求解最短/最长覆盖子串，典型题如最小覆盖子串。
LeetCode 热门 100 题中，有三道题分别代表了上述三种范式的经典应用：560. 和为 K 的子数组（前缀和+哈希）、239. 滑动窗口最大值（单调队列）、76. 最小覆盖子串（滑动窗口+频次计数）。下面逐一拆解。
1. 和为 K 的子数组（LeetCode 560）
题目：给定整数数组 nums 和整数 k，统计连续子数组之和等于 k 的个数。
暴力法：枚举所有子数组 (i, j)，累加求和并计数，时间复杂度 O(n²)。
优化思路（前缀和 + 哈希表）：
设前缀和 pre[i] = nums[0] + ... + nums[i]，则子数组 (j, i] 的和 = pre[i] - pre[j-1]。要使其等于 k，等价于 pre[j-1] = pre[i] - k。因此，在遍历 i 时，只需查找之前出现过多少个前缀和等于 pre[i] - k，累加计数。用哈希表存储前缀和出现次数，初始放入 {0: 1} 代表空前缀。
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += prefixCount.getOrDefault(sum - k, 0);
prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) + 1);
}
return count;
}
复杂度：时间 O(n)，空间 O(n)。
关键点：先查 target 再更新当前前缀和，避免 k=0 时将自身计入；哈希表存储频次而非布尔值，因为可能存在多个相同前缀和。
2. 滑动窗口最大值（LeetCode 239）
题目：给定数组 nums 和窗口大小 k，从左向右滑动窗口，返回每个窗口中的最大值。
暴力法：每个窗口扫描 k 个元素求最大值，总时间复杂度 O(n·k)。
优化思路（单调队列）： 维护一个双端队列（Deque），其中存储数组下标，且队列中下标对应的元素值 严格单调递减。这样队首始终是当前窗口最大值的下标。窗口滑动时：
- 移除队首出界的下标（
index < i-k+1）。 - 从队尾移除所有小于当前元素值的下标（因为它们不可能成为后续窗口的最大值）。
- 将当前下标加入队尾。
- 若窗口已形成（
i >= k-1），队首即为当前窗口最大值。
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || k == 0) return new int[0];
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
复杂度：每个元素入队出队各一次，时间 O(n)，空间 O(k)。
关键点：队列存储下标便于判断是否出界；单调性确保队首始终最大；新元素从队尾踢掉所有比自己小的元素。
3. 最小覆盖子串（LeetCode 76）
题目：给定字符串 s 和 t，在 s 中找到包含 t 中所有字符（含重复次数）的最短子串，若不存在返回空串。
优化思路（滑动窗口 + 频次计数器）：
- 用
need哈希表记录 t 中每个字符的需求量，用window记录当前窗口内各字符出现次数。 - 用
formed记录当前窗口内满足需求（频次 >= need）的 字符种类数，当formed == need.size()时窗口已经覆盖所有字符。 - 右指针
right不断右移，加入新字符并更新window和formed。 - 当
formed == required时，尝试收缩左指针left，在收缩过程中不断更新最小长度和起始位置，同时更新window和formed，直到不再满足条件。
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int formed = 0, required = need.size();
int minLen = Integer.MAX_VALUE, start = 0;
while (right < s.length()) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
formed++;
}
while (left <= right && formed == required) {
c = s.charAt(left);
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
window.put(c, window.get(c) - 1);
if (need.containsKey(c) && window.get(c).intValue() < need.get(c).intValue()) {
formed--;
}
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
复杂度：时间 O(n + m)，空间 O(k)（k 为字符集大小）。
关键点：formed 记录的是种类数（去重），只有当某个字符的窗口频次 恰好等于 需求频次时才加一，减一同样在恰好小于时发生；收缩时要先更新答案再移出左字符。
三题对比与启发
| 题目 | 核心技巧 | 数据结构 | 时间复杂度 | 空间复杂度 | 典型特征 |
|---|---|---|---|---|---|
| 和为 K 的子数组 | 前缀和 + 哈希表 | HashMap | O(n) | O(n) | 统计区间和等于目标值的数量 |
| 滑动窗口最大值 | 单调队列 | Deque | O(n) | O(k) | 维护固定窗口内最值 |
| 最小覆盖子串 | 双指针滑动窗口 + 频次计数 | HashMap + 双指针 | O(n) | O(k) | 求最短覆盖子串 |
共同本质：三者都利用了某种 “增量维护” 的思想，在遍历过程中实时更新状态，避免重复计算。前缀和哈希将区间和查询变为差值查询；单调队列在 O(1) 内获取窗口最值；滑动窗口通过双指针和频次计数器动态伸缩。
不同侧重：
- 560：依赖累积和的线性关系，配合哈希表快速查找目标值。
- 239：借助单调性剔除不可能成为答案的元素，保持队列有序。
- 76：利用双指针伸缩窗口，并在满足条件时收缩以寻找最优解。
总结：子串与子数组模块的核心心法
子串/子数组问题的优化核心在于"复用历史信息"。无论是前缀和的累加结果、单调队列维护的极值，还是滑动窗口内的频次状态，都避免了每次重新扫描整个区间。
解题时的思考路径：
- 若问题涉及 区间求和 或 计数，优先考虑前缀和 + 哈希表。
- 若问题涉及 固定窗口的最值，使用单调队列。
- 若问题涉及 动态窗口的最优覆盖或约束，使用双指针滑动窗口，配合状态变量。
- 若上述均不适用，再考虑其他复杂方法（如 DP、分治等）。
掌握这三道题，你就掌握了数组/字符串子区间问题中最常用的三种优化利器。