一、和为 K 的子数组
中等
题目：给定整数数组 nums 和整数 k，统计并返回数组中和值为 k 的子数组（连续非空子序列）的个数。
示例：
输入：nums = [1,2,3], k = 3
输出：2提示：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
1.1 暴力起手（明显超时）
/**
* 560.和为 K 的子数组（暴力）
*
* @param nums 提供的数组
* @param k 目标和
* @return 和为k的子序列个数
*/
public int subarraySum(int[] nums, int k) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) ans++;
}
}
return ans;
}1.2 思路优化
上述暴力解法，数据利用率低下，每次都得重新求和，区间和存在重复计算
- 等会，如果我们去掉的重复区间，不就是一个子序列吗？
a[i] + a[i + 1] + ... + a[j] = ( a[0] + a[1] + a[2] + ... + a[j] ) - ( a[0] + a[1] + a[2] + ... + a[i - 1] )
下面引入前缀和的概念
为了方便推导，通常把前缀和数组定义为：
- prefix[0] = 0
- prefix[i] = nums[0] + nums[1] + … + nums[i-1] （i >= 1）
这样，区间 [a, b]（以 0 为起始索引，且 a <= b）的和可以写成：
sum(nums[a..b]) = prefix[b+1] - prefix[a]1.3 前缀和
若某个子数组 nums[a..b] 的和为 k，则
prefix[b+1] - prefix[a] = k ==> prefix[a] = prefix[b+1] - k当遍历到位置 j（对应 prefix = prefix[j+1]）时，需要知道有多少个 i（即 prefix[i]）满足 prefix[i] = prefix[j+1] - k。用哈希表 count 记录各个前缀和出现的次数，遍历时累加 count.get(prefix - k) 即可。
初始化时把 count.put(0, 1)（表示空前缀和出现一次，方便统计从数组开头就能凑出 k 的情况）
/**
* 560.和为 K 的子数组（前缀和）
*
* @param nums 提供的数组
* @param k 目标和
* @return 和为k的子序列个数
*/
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>(nums.length + 1, 1);
int ans = 0, prefix = 0;
count.put(0, 1);
for (int a : nums) {
prefix += a;
ans += count.getOrDefault(prefix - k, 0);
count.put(prefix, count.getOrDefault(prefix, 0) + 1);
}
return ans;
}执行用时分布22ms，击败83.68%，复杂度O(N)
消耗内存分布48.42MB，击败5.02%，复杂度O(N)
1.4 为什么不用滑动窗口
- 滑动窗口（sum >= k 收缩）只在数组全部非负时才成立。
- 本题会出现0，扩张收缩需讨论
- 本题允许负数，不能用该策略，否则会漏计或错计。
二、滑动窗口的最大值
困难
题目：给你一个整数数组 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 <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
2.1 暴力起手（明显超时）
/**
* 239.滑动窗口最大值（暴力）
*
* @param nums 提供的数组
* @param k 窗口大小
* @return 最大元素数组
*/
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < res.length; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
max = nums[j] > max ? nums[j] : max;
}
res[i] = max;
}
return res;
}2.2 思路优化
因为每次移动窗口时，移除了左窗口元素 left，新增加一个右窗口元素 right
- 设每次移动窗口前，最大值为 max
- 如果移除的 left 不是最大值，只需要比较 max 和 right 的值就可以了
- 如果移除的 left 是最大值，则需要比较 第2大的元素和 right
- 这种比较最大元素（可能是第2大元素）与新插入元素，在 347.前K个高频元素↗ 这一题中有出现过，解决方案为堆排或优先队列
/**
* 239.滑动窗口最大值（堆排序）
*
* @param nums 提供的数组
* @param k 窗口大小
* @return 最大元素数组
*/
public int[] maxSlidingWindow(int[] nums, int k) {
// 1、维护一个从大到小排列的优先队列
// 滑动窗口移动时
// - 如果移除的不是最大值，直接比较队首元素和新插入的的元素
// - 如果移除的是最大值，先弹出队首元素
// * 队列中存储元素下标？元素值？
// - 存下标可以便捷判断下标是否过期
// PriorityQueue 默认最小堆，若需最大堆则提供 comparator（例如 Integer.compare(nums[b], nums[a])）
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> nums[b] - nums[a]);
for (int i = 0; i < k; i++) {
pq.add(i);
}
int[] ans = new int[nums.length - k + 1];
ans[0] = nums[pq.peek()];
for (int i = k; i < nums.length; i++) {
// 举例：int[] nums = {1, 1, 1, 1};
// 举例：k = 2，初始0, 1
// - 👇 head = 0, i = 2, 0 = i - k
// 移除堆顶所有已过期的下标（<= i - k）
while (!pq.isEmpty() && pq.peek() <= i - k) {
pq.poll();
}
pq.add(i);
ans[i - k + 1] = nums[pq.peek()];
}
return ans;
}执行用时分布85ms，击败13.77%，复杂度O(Nlogk) 消耗内存分布141.79MB，击败28.18%，复杂度O(K)
2.3 注意力惊人环节
1、注意到击败人数太少，还能再凹
2、注意到优先队列底层结构是堆，每次插入删除 heapify 开销较大，是否能通过普通队列替换？
- 如何排序初始窗口中的元素？（nums[0] 到 nums[k - 1]）
- 按👇方式移除过期元素，插入新的元素时，如何将元素插入到降序排序的正确位置？
// 移除堆顶所有已过期的下标（<= i - k）
while (!pq.isEmpty() && pq.peek() <= i - k) {
pq.poll();
}3、每次加入元素x到窗口最右边，注意到
- 秉承着比较最大元素（可能是第2大元素）与新插入元素的思想
- x此时在窗口最右边，由于窗口向右移动，x一定比其左边的元素晚离开窗口
- 所以原先窗口内所有比x小的可以全部忽略
- 我们只需要不断弹出被忽略的元素，然后取出队首元素即可
- 因为队列是降序排序，注意到普通队列Queue只能弹出队首元素，没法弹出队尾，故采用双端队列
/**
* 239.滑动窗口最大值（单调队列）
*
* @param nums 提供的数组
* @param k 窗口大小
* @return 最大元素数组
*/
public int[] maxSlidingWindow(int[] nums, int k) {
int[] ans = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
deque.pollLast();
}
deque.addLast(i);
}
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < nums.length; i++) {
// 1. 移除队首过期下标（下标 <= i - k）
while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 2. 弹出所有比 nums[i] 小的队尾元素
while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
deque.pollLast();
}
deque.addLast(i);
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}执行用时分布30ms，击败77.08%，复杂度O(N)
消耗内存分布，152.51MB，击败7.74%，复杂度O(K)
三、最小覆盖子串
困难
题目：给定字符串 s 和字符串 t，找出 s 中包含 t 所有字符（含频次）且长度最短的子串。若不存在，返回空串。
示例：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
输入：s = "a", t = "aa"
输出：""提示：
m == s.lengthn == t.length1 <= m, n <= 10^5s和t由英文字母组成
3.1 暴力（难实现）
看了一下前文，发现刚刚学了前缀和，难道可以用的上？
由于我们只关心 t 中出现的字符次数 <= s 字串中相应出现的字符次数
- 所以我们可以利用字符串前缀和，先把 s 和 t 中的字符存入
- 不难发现，太复杂了
Map<Character, Integer> smap = new HashMap<>();
Map<Character, Integer> tmap = new HashMap<>();
// ∵ smap[r] - smap[l] = tmap
// ∴ smap[l] = smap[r] - tmap
// 存储所有smap的前缀和快照
Map<Integer, Map<Character, Integer>> map = new HashMap<>();
if (map包含smap[l]) 说明存在，记录当前起始位置和长度- 前缀和只适用于“等于”型问题，范围和最值不适用
3.2 再次尝试暴力破解
由于要收缩到最小区间，可以考虑使用双指针
由于是最小区间，所以第一个元素和最后一个元素一定是 t 中的字符
因此先从左到右移动左指针 left 指向 t 中字符第一次出现的位置，从右到左移动右指针 right 做相同的事情
- 统计初始指向区间中的字母频数
如何统计字符出现次数？
- 注意到题目说
s和t由英文字母组成，所以可以预分配一个长度52的数组存储字母
- 注意到题目说
如何收缩区间？
- 判断当前边界字母的频数是否 > t 中对应字母的频数，如果大于则可以收缩，如果等于，则不能再收缩了，边界固定
输入：s = "CooBoooAoooC", t = "ABC"
输出："CooBoooA"
此情况下，初始指向字母相同，无法确定先收缩哪边，考虑回溯？ 可以发现初始范围过大，而且收缩过程回溯复杂，体育老师说的好，正难则反，考虑扩张区间
3.3 思路优化
- 首先，确定左边界
- 如何判断当前区间已满足题意？
- 新设2个
int变量required用于记录t中不同字母的数量satisfy用于记录当前区间已满足频数的字母数量- 不断向右扩张区间
- 当
satisfy == required时，说明当前区间已满足题意，判断当前区间长度是否为新的最小值，并尝试移动左边界
输入：s = "BoooAoooCBooo", t = "ABC"
第一步：BoooAoooC
- 满足，记录最小值，尝试收缩
- oooAoooC，不满足，退出收缩
第二步：oooAoooCB
- 满足，记录最小值，尝试收缩
- AoooCB，收缩
- ... 实现如下
/**
* 76. 最小覆盖子串（双指针）
*
* @param s 被查找的字符串
* @param t 要查找的字符串
* @return 最小字串
*/
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
int[] ts = new int[52];
int required = 0; // 不同字符的数量
for (char c : t.toCharArray()) {
int id = index(c);
if (ts[id] == 0) required++;
ts[id]++;
}
int l = 0, r = 0;
int[] window = new int[52];
// 确定左边界
while (l < t.length() && !t.contains(s.charAt(l) + "")) l++;
if (l >= s.length()) return "";
// 已满足频率的字母数
int satisfy = 0;
int minLen = Integer.MAX_VALUE, minL = 0;
char[] ss = s.toCharArray();
while (r < ss.length) {
int idr = index(ss[r]);
window[idr]++;
if (window[idr] == ts[idr]) satisfy++;
while (l <= r && satisfy == required) {
// 更新答案
if (r - l + 1 < minLen) {
minLen = r - l + 1;
minL = l;
}
// 尝试移除左侧字符
int idl = index(ss[l]);
window[idl]--;
// 如果移除后的区间不满足所需频数，终止循环
if (ts[idl] > 0 && window[idl] < ts[idl]) {
satisfy--;
}
l++;
}
r++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minL, minL + minLen);
}
private int index(char c) {
if (c >= 'A' && c <= 'Z') return c - 'A';
return 26 + (c - 'a');
}执行用时分布5ms，击败80.92%，复杂度O(N)
消耗内存分布45.79MB，击败20.66%，复杂度O(1)
Thanks for reading!
力扣hot100-《子串》章节题解
周四 12月 11 2025 子串
2968 字 · 17 分钟