以下摘自leetcode Top100精选题目-子串篇
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例:
示例 1：
输入：nums = [1,1,1], k = 2
输出：2Solution:
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1); // 前缀和为0的次数初始化为1，代表空子数组
int currentSum = 0;
int result = 0;
for (int num : nums) {
currentSum += num;
// 查找是否存在前缀和为 currentSum - k 的子数组
if (prefixSumCount.containsKey(currentSum - k)) {
result += prefixSumCount.get(currentSum - k);
}
// 更新前缀和的计数
prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
}
return result;
}- 初始化一个哈希表
prefixSumCount，用来存储前缀和出现的次数，初始时前缀和为0的出现次数为1（表示空子数组的和）。 - 初始化一个变量
currentSum来累计当前的前缀和。 - 遍历数组
nums，对于每个元素，将其加到currentSum上，并查看currentSum - k是否在prefixSumCount中。如果在，说明从某个前缀和到当前位置的和为k，因此将其对应的计数加到结果中。 - 将
currentSum在prefixSumCount中的计数加1，表示当前的前缀和出现了一次。 - 遍历结束后，结果就是和为
k的子数组的数量。
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例:
输入：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] 7Solution:
可以使用双端队列（Deque）来高效解决。双端队列可以在两端进行插入和删除操作，非常适合用来维护一个动态调整的窗口（滑动窗口）
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
Deque<Integer> deque = new LinkedList<>(); // 双端队列，存储数组索引
int[] result = new int[nums.length - k + 1]; // 存储结果的最大值
// 处理第一个窗口
for (int i = 0; i < k; i++) {
// 清除deque中不在窗口范围内的索引，并保证deque的前端是最大值的索引
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
// 处理剩余窗口
for (int i = k; i < nums.length; i++) {
// 记录当前窗口的最大值
result[i - k] = nums[deque.peekFirst()];
// 清除deque中已经不在窗口范围的索引
while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 维护deque，确保最大值的索引在前端
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
// 记录最后一个窗口的最大值
result[nums.length - k] = nums[deque.peekFirst()];
return result;
}
} 先初始化一个双端队列deque来存储数组中最大值的索引，以及一个结果数组result来存放每个窗口的最大值。算法分为两个阶段：初始化第一个窗口和滑动窗口更新。在初始化阶段，通过比较将最大值的索引存入队列。随着窗口向右滑动，不断地从队列头部移除不在窗口内的索引，并根据新进入窗口的元素更新队列，确保队列前端始终指向当前窗口内的最大值索引。将每个窗口的最大值依次存入结果数组并返回。
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例:
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。Solution:
public class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
// 记录目标字符串t中每个字符需要的个数
int[] targetCharCount = new int[128];
for (char c : t.toCharArray()) {
targetCharCount[c]++;
}
// 左右指针定义窗口的边界
int left = 0, right = 0;
// 记录符合条件的最小窗口的起始索引及长度
int start = 0, minLen = Integer.MAX_VALUE;
// 当前窗口内各个字符的数量
int formed = 0;
// 当右指针未越界时循环
while (right < s.length()) {
char c = s.charAt(right);
// 如果目标字符串需要当前字符，则更新formed计数
if (targetCharCount[c] > 0) {
formed++;
}
// 更新当前字符在窗口中的计数
targetCharCount[c]--;
right++;
// 当窗口内的字符已经符合要求时，尝试缩小窗口
while (formed == t.length()) {
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char leftChar = s.charAt(left);
// 恢复左指针指向字符的计数
targetCharCount[leftChar]++;
// 如果恢复计数后，该字符的计数大于0，说明它不再是我们所需要的字符了
if (targetCharCount[leftChar] > 0) {
formed--;
}
left++;
}
}
// 如果minLen仍为初始值，说明没有符合条件的子串
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
} 先通过一个数组targetCharCount记录目标字符串t中每个字符的需求量。使用两个指针left和right定义一个滑动窗口，并通过变量formed来追踪窗口内是否已经包含了t中的所有字符。当窗口内的字符组合满足条件时，尝试收缩窗口左边界以寻找最小覆盖子串。在循环过程中，不断更新最小覆盖子串的起始索引和长度。如果找到符合条件的子串，则返回该子串；否则，返回空字符串。