class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;//
// key：前缀和，value：key 对应的前缀和的个数
HashMap<Integer, Integer> mp = new HashMap<>();
// 对于下标为 0 的元素，前缀和为 0，个数为 1
mp.put(0, 1);
for(int i = 0;i < nums.length;i++){
pre += nums[i];//前辍和
if(mp.containsKey(pre - k)){// 先获得前缀和为 pre - k 的个数，加到计数变量里
count += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);// 然后维护 mp 的定义
}
return count;
}
}//利用双端队列手动实现单调队列
/**
* 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n - k + 1];
int idx = 0;
for(int i = 0; i < n; i++) {
// 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
// 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
while(!deque.isEmpty() && deque.peek() < i - k + 1){
deque.poll();
}
// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
if(i >= k - 1){
res[idx++] = nums[deque.peek()];
}
}
return res;
}
}class Solution {
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);//记录字符串t中每个字符出现的次数
}
int left = 0, right = 0;//滑动窗口的左右边界
int valid = 0;//对应需要的值
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {//右指针小于s时
char c = s.charAt(right);//更新有边界
right++;
if (need.containsKey(c)) {//如果当前更新的值等于need中需要的字符串
window.put(c, window.getOrDefault(c, 0) + 1);//更新窗口的值
if (window.get(c).equals(need.get(c))) {//如果字符需要的值已经对上窗口的值，证明这个字符串已经够了，valid++
valid++;
}
}
while (valid == need.size()) {//当窗口中包含了字符串t中的所有字符时,开始缩小窗口的大小,直到窗口中不再包含字符串t中的所有字符。
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;//更新左边界，缩小
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);//返回结果
}
}后面两道hard题非常有难度。
首先560利用了前辍和，把contains(pre - k)即符合当前情况的value全部加到count上面 从而实现了计数功能。
239关键就是利用双端队列手动实现单调队列。使得队列中不断维护一个左边是最大的队列，如果不是就弹出。
76的重点就是valid，把每个字母需要的次数单独提出来，当全部valid后，就开始缩小窗口，返回最小覆盖子串，直到valid对不上为止。
Comments NOTHING