76. 最小覆盖子串题目链接76. 最小覆盖子串 - 力扣LeetCode题目描述给你字符串s和字符串t请你找出s中包含t所有字符的最短连续子串如果没有返回空串。核心思路这道题是滑动窗口的经典难题核心思想用两个哈希表need记录t中每个字符需要的数量window记录当前窗口内字符的数量右指针right不断向右扩大窗口当窗口完全包含 t 所有字符时尝试移动左指针left缩小窗口寻找最小长度全程记录最小窗口的起始位置和长度最后截取结果代码实现逐行注释class Solution { public String minWindow(String s, String t) { // 边界判断空字符串直接返回空 if (s null || s.isEmpty() || t null || t.isEmpty()){ return ; } // 记录 t 中字符的需求量 MapCharacter,Integer need new HashMap(); // 记录当前窗口内字符的数量 MapCharacter,Integer window new HashMap(); int left 0, right 0; // 滑动窗口左右指针 int strnumber 0; // 已匹配成功的字符种类数 int minlen Integer.MAX_VALUE; // 最短子串长度 int start 0; // 最短子串起始位置 // 初始化 need 哈希表 for(char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } // 右指针移动扩展窗口 while(right s.length()){ char r s.charAt(right); right; // 如果当前字符在 t 中更新窗口计数 if(need.containsKey(r)){ window.put(r, window.getOrDefault(r, 0) 1); // 该字符数量匹配成功 if (need.get(r).equals(window.get(r))) { strnumber; } } // 窗口已完全包含 t 所有字符开始收缩左边界 while (strnumber need.size()){ // 更新最小窗口 if (right - left minlen){ start left; minlen right - left; } // 左指针右移尝试缩小窗口 char l s.charAt(left); if (window.containsKey(l)){ window.put(l, window.get(l) - 1); // 该字符不再满足要求匹配数减少 if (window.get(l) need.get(l)) { strnumber--; } } left; } } // 没有符合条件的子串返回空否则截取结果 return minlen Integer.MAX_VALUE ? : s.substring(start, start minlen); } }239. 滑动窗口最大值题目链接239. 滑动窗口最大值 - 力扣LeetCode题目描述给你一个数组nums有一个大小为k的窗口从左端滑到右端你只能看到窗口内的k个数字返回每个窗口的最大值。核心思路这道题不能暴力遍历否则超时。正确解法自定义单调队列 滑动窗口核心规则维护一个单调递减队列队首永远是当前窗口最大值加入元素时比当前元素小的全部弹出保持队列递减弹出元素时只有要移除的元素 队首才真正弹出队首就是当前窗口最大值代码实现自定义单调队列 逐行注释// 自定义单调递减队列 class Mydeque{ DequeInteger deque new LinkedList(); // 弹出元素判断是否为队首最大值 void poll(int val){ if(!deque.isEmpty() val deque.peek()){ deque.poll(); } } // 添加元素比当前值小的全部移除保持单调递减 void add(int val){ while(!deque.isEmpty() val deque.getLast()){ deque.removeLast(); } deque.add(val); } // 获取队首当前窗口最大值 int peek(){ return deque.peek(); } } class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int len n - k 1; int[] res new int[len]; // 存储每个窗口最大值 int index 0; Mydeque mydeque new Mydeque(); // 先把第一个窗口的元素加入队列 for(int i 0; i k; i){ mydeque.add(nums[i]); } res[index] mydeque.peek(); // 开始滑动窗口 for(int i k; i n; i){ // 移除窗口左边移出的元素 mydeque.poll(nums[i - k]); // 添加窗口右边新进入的元素 mydeque.add(nums[i]); // 记录当前窗口最大值 res[index] mydeque.peek(); } return res; } }博客总结这两道题是滑动窗口最常考的难题也是面试高频手撕题最小覆盖子串双哈希表 滑动窗口找最短包含子串滑动窗口最大值自定义单调队列 滑动窗口O (n) 高效求解