hot100子串

滑动窗口模板int left 0, right 0;int valid 0;// 各类辅助变量如最短长度 minLen、最长长度 maxLen、起始位置 start...while (right n) {char c s[right];right;// 【1. 扩大窗口】更新 window 频次、valid 状态// 【2. 判断收缩】这里的条件视题目而定// 求最短 (76题)while (valid needSize) → 满足条件就缩// 求最长 (3题) while (window[c] 1) → 不满足条件就缩// 定长求异位词 (438题)while (right - left p.length()) → 长度到了就缩while (窗口需要收缩) {// 【3. 更新答案】求最短在这里更新因为目前是合法状态// ...char d s[left];left;// 【4. 缩小窗口】更新 window 频次、valid 状态}// 【注意】如果是求最长 (LC 3)答案在 while 循环外面更新因为缩完之后才是合法的最大窗口}560. 和为 K 的子数组 - 力扣LeetCode不用滑动窗口因为有负数前缀和 哈希表和两数之和类似存一个map记录每种前缀和的次数如果map存在presunm[i]-k就加上对应的value。class Solution { public int subarraySum(int[] nums, int k) { int presum0; int res0; HashMapInteger, Integer countnew HashMap(); count.put(0,1); for(int i0;inums.length;i){ presumnums[i]; if(count.containsKey(presum-k)){ rescount.get(presum-k); } count.put(presum, count.getOrDefault(presum, 0)1); } return res; } }76. 最小覆盖子串 - 力扣LeetCode滑动窗口1. 状态判定以need和window频次数组为基准用valid记录“已达标字符种类数”来代替遍历比对。2. 状态维护右指针进窗、左指针出窗时必须同步对称地更新窗口频次并精准控制valid的加减。class Solution { public String minWindow(String s, String t) { // 1. 特判如果 s 比 t 还短绝对不可能包含 t直接返回空串 if (s.length() t.length()) { return ; } // window 数组记录当前滑动窗口中每个字符出现的实际次数 int[] window new int[128]; // need 数组记录目标字符串 t 中每个字符需要的次数 int[] need new int[128]; int needSize 0; // 记录 t 中有多少种【不同】的字符 // 2. 统计 t 的字符信息 for (int i 0; i t.length(); i) { char c t.charAt(i); // 如果是第一次遇到这个字符说明发现新种类了 if (need[c] 0) { needSize; } need[c]; } int left 0; // 滑动窗口的左边界 int start 0; // 记录最终最小覆盖子串的起始下标 int minLen Integer.MAX_VALUE; // 记录最小覆盖子串的长度初始为无穷大 int valid 0; // 记录当前窗口内有多少【种】字符的数量已经达标了 // 3. 开始遍历 sright 是滑动窗口的右边界 for (int right 0; right s.length(); right) { char c s.charAt(right); // 进窗操作 window[c]; // 当前字符进入窗口频次 1 // 如果这个字符是 t 需要的判断是否【刚好】凑齐 if (need[c] 0 window[c] need[c]) { valid; // 刚好达标达标种类 1 } // 缩窗操作 // 当 valid needSize 时说明当前窗口已经完全覆盖了 t // 这是一个合法的窗口我们要尝试把左边界往右缩看看能不能找到更短的 while (valid needSize) { // 4. 更新最优解如果当前窗口长度比之前记录的还短就更新 if (right - left 1 minLen) { start left; minLen right - left 1; } // 5. 准备将最左边的字符移出窗口 char remove s.charAt(left); left; // 左边界向右移动 // 如果移出的是 t 需要的字符 if (need[remove] 0) { // 【关键点】如果移出前它的数量刚好等于 t 需要的数量 // 说明移出后它就不够了达标种类要减 1 if (window[remove] need[remove]) { valid--; } // 无论是否达标窗口里的实际数量必须减 1 window[remove]--; } } // 退出 while 循环说明 valid needSize窗口不合法了right 继续往右扩 } // 6. 返回结果如果 minLen 没被更新过说明没找到返回空串否则截取最小子串 return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } }239. 滑动窗口最大值 - 力扣LeetCode滑动窗口单调队列时间复杂度n一种不优雅的写法能通过每次删除leftclass Solution { public int[] maxSlidingWindow(int[] nums, int k) { DequeInteger queuenew LinkedList(); int left0; int []resnew int[nums.length-k1]; int idx0; for(int right0;rightnums.length;right){ while(queue.size()0 nums[queue.peekLast()]nums[right]){ queue.pollLast(); } queue.offerLast(right); if(right-left1k){ res[idx]nums[queue.peekFirst()]; queue.remove(left); left; } } return res; } }清理队头的逻辑变了left窗口左边界永远一定小于等于queue.peekFirst()队头元素的下标当窗口向右滑动左边界left移动时会发生以下三种情况left queue.peekFirst()left被入队时候清理过了left queue.peekFirst()相等的时候说明left的位置一直是最大值没有被入队清理如果再往右滑一步它就过期了。所以在记录完当前窗口的最大值后必须立刻pollFirst()把它请出去。left queue.peekFirst不存在因为队列元素就在窗口内class Solution { public int[] maxSlidingWindow(int[] nums, int k) { DequeInteger queuenew LinkedList(); int left0; int []resnew int[nums.length-k1]; int idx0; for(int right0;rightnums.length;right){ while(queue.size()0 nums[queue.peekLast()]nums[right]){ queue.pollLast(); } queue.offerLast(right); if(right-left1k){ res[idx]nums[queue.peekFirst()]; if (queue.peekFirst() left) { queue.pollFirst(); } left; } } return res; } }