LeetCode Hot 100：子串
Leetcode Hot 100
子串
和为 K 的子数组
题目：给你一个整数数组
nums和一个整数k，请你统计并返回 该数组中和为k的子数组的个数。（子数组是数组中元素的连续非空序列。）解决：
暴力枚举：两层循环遍历
1
2
3
4
5
6
7
8
9
10
11
12
13public int subarraySum(int[] nums, int k) {
int res = 0;
for(int left = 0; left < nums.length; left++) {
int sum = 0;
for(int right = left; right < nums.length; right++){//以left为开头，符合的子数组
sum += nums[right];
if(sum == k){
res++;
}
}
}
return res;
}前缀和+哈希表优化：哈希表存储存在的前缀和的个数
1
2
3
4
5
6
7
8
9
10
11
12
13public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap<Integer, Integer> mp = new HashMap<>();//哈希表存储前缀和个数
mp.put(0, 1);//前缀和为0的有1个
for(int i = 0; i < nums.length; i++){
pre += nums[i];//当前前缀和
if(mp.containsKey(pre - k)){
count += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
滑动窗口最大值
题目：整数数组
nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。解决：
优先队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public int[] maxSlidingWindow(int[] nums, int k) {
//优先队列
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] p1, int[] p2){
return p1[0] != p2[0] ? p2[0] - p1[0] : p2[1] - p1[1];
}
});
for(int i=0; i<k; i++){//把前k个数放入优先队列，存放值和下标
pq.offer(new int[]{nums[i], i});
}
int[] res = new int[nums.length - k + 1];//存放结果的数组
res[0] = pq.peek()[0];
for(int i=k; i<nums.length; i++){
pq.offer(new int[]{nums[i], i});//新元素放入优先队列
while(pq.peek()[1] <= i-k){//当堆顶的元素已经不在窗口内，删除
pq.poll();
}
res[i-k+1] = pq.peek()[0];//当前窗口的最大值就算堆顶元素
}
return res;
}单调队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26public int[] maxSlidingWindow(int[] nums, int k) {
//单调队列：队列中存储递减的区间下标
Deque<Integer> deque = new LinkedList<>();
for(int i=0; i<k; i++){//存储第一个大小为k的窗口中递减的下标
while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
deque.pollLast();//删除比当前值小的
}
deque.offerLast(i);
}
int[] res = new int[nums.length - k + 1];//存放结果的数组
res[0] = nums[deque.peekFirst()];//当前队列头就是窗口最大值
for(int i=k; i<nums.length; i++){
while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
deque.pollLast();//删除比当前值小的
}
deque.offerLast(i);//到这里和上面加入窗口的一样，下面还需要删除不在窗口中的数
while(deque.peekFirst() <= i-k){//删除不在滑动窗口中的数
deque.pollFirst();
}
res[i-k+1] = nums[deque.peekFirst()];
}
return res;
}分块+预处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30public int[] maxSlidingWindow(int[] nums, int k) {
//分块+预处理
//每个分块大小为k，进行分块
int[] prefixMax = new int[nums.length];//以i为结尾的后缀的分块的最大值
int[] suffixMax = new int[nums.length];//以i为开始的前缀的分块的最大值
for(int i=0; i<nums.length; i++){//后缀最大值从头开始更新
if(i%k == 0){
prefixMax[i] = nums[i];
}else{
prefixMax[i] = Math.max(prefixMax[i-1], nums[i]);
}
}
for(int i=nums.length-1; i>=0; i--){//前缀最大值从尾开始更新
if(i%k == 0 || i == nums.length-1){
suffixMax[i] = nums[i];
}else{
suffixMax[i] = Math.max(suffixMax[i+1], nums[i]);
}
}
int[] res = new int[nums.length - k + 1];
for(int i=0; i<=nums.length-k; i++){
res[i] = Math.max(suffixMax[i], prefixMax[i+k-1]);
//以i为开头的前缀的最大值和以i+k-1为结尾的最大值中的最大值即为该窗口最大值
}
return res;
}
最小覆盖子串
题目：给你一个字符串
s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。比如：1
2
3输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。解决：
滑动窗口：先更新该窗口，然后不断收缩当前符合条件的窗口，找到最小的子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49class Solution {
Map<Character, Integer> ori = new HashMap<>();
Map<Character, Integer> cnt = new HashMap<>();
public String minWindow(String s, String t) {
for(int i=0; i<t.length(); i++){//存储字符串t中各个字符的个数
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int len = Integer.MAX_VALUE;
int resLeft = -1;
int resRight = -1;
for(int left=0,right = 0; right<s.length(); right++){
if(right < s.length() && ori.containsKey(s.charAt(right))){
//如果当前字母在t中出现，更新cnt表
cnt.put(s.charAt(right), cnt.getOrDefault(s.charAt(right), 0) + 1);
}
//判断当前cnt表是否符合要求，同时收缩窗口
while(check() && left <= right){
if(right - left + 1 < len){//更新当前最小的符合子串
len = right - left + 1;
resLeft = left;
resRight = right + 1;
}
if(ori.containsKey(s.charAt(left))){//收缩窗口，更新cnt表
cnt.put(s.charAt(left), cnt.getOrDefault(s.charAt(left), 0) - 1);
}
left++;//收缩窗口则left++
}
}
return resLeft == -1 ? "" : s.substring(resLeft, resRight);
}
public boolean check(){//判断cnt中字符个数是否满足ori的要求
//遍历Map
Iterator iter = ori.entrySet().iterator();
while(iter.hasNext()){
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if(cnt.getOrDefault(key, 0) < val){
//只要cnt中该字符大于等于ori中字符，都满足要求
return false;
}
}
return true;
}
}滑动窗口（优化）：通过count数组存储不同，differ维护不同字符的个数。和【438. 找到字符串中所有字母异位词】这道题的优化思路一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class Solution {
public String minWindow(String s, String t) {
//优化：通过count数组存储不同，differ维护不同字符的个数
if(t.length() > s.length()){
return "";
}
int[] count = new int[128];//存储字符个数
int differ = 0;//s和t中不同字符的个数
for(int i=0; i<t.length(); i++){
char ch = t.charAt(i);
if(count[ch] == 0){
differ++;//不同的字符的个数
}
count[ch]++;
}
int resLeft = -1;
int resRight = s.length();
for(int left=0, right = 0; right<s.length(); right++){
count[s.charAt(right)]--;
//s中存在该字符，则缺少的个数减一；如果s中存在的字符t中不存在，这里会变成负数，不用考虑
if(count[s.charAt(right)] == 0){
differ--;
}
while(differ == 0 && left <= right){//符合要求
if(right - left < resRight - resLeft){
//如果当前符合的子串更小，更新为当前子串
resRight = right;
resLeft = left;
}
//收缩窗口
char ch = s.charAt(left);
if(count[ch] == 0){
differ++;
}
count[ch]++;//收缩左端点left，则s中缺少该字符的个数加一
left++;//收缩左端点
}
}
return resLeft == -1 ? "" : s.substring(resLeft, resRight+1);
}
}
LeetCode Hot 100：子串
http://surourou8.github.io/2025/04/12/LeetCode-Hot-100：子串/