【力扣hot100】子串专题：暴力、前缀和、滑动窗口与单调队列

子串专题文章目录子串专题560. 和为 K 的子数组暴力前缀和哈希表239. 滑动窗口最大值单调队列队尾操作当队列用队首操作当队列用栈操作当栈用76. 最小覆盖子串560. 和为 K 的子数组560. 和为 K 的子数组暴力遍历得到所有子串并求和 筛选出符合条件的classSolution{publicintsubarraySum(int[]nums,intk){intans0;intnnums.length;for(inti0;in;i){//列举每个元素当子串结尾的情况intsum0;for(intji;j0;j--){//求所有以这个子串为结尾的和sumnums[j];if(sumk)ans;}}returnans;}}前缀和哈希表前缀和pre[i]pre[i−1]nums[i][j…i] 这个子数组和为 k这个条件我们可以转化为pre[i]−pre[j−1]k简单移项可得符合条件的下标 j 需要满足pre[j−1]pre[i]−kclassSolution{publicintsubarraySum(int[]nums,intk){intans0,pre0;intnnums.length;HashMapInteger,IntegermpnewHashMap();// 记录前缀和及其出现次数mp.put(0,1);// 前缀和为0的有一个for(inti0;in;i){prenums[i];if(mp.containsKey(pre-k)){ansmp.get(pre-k);}mp.put(pre,mp.getOrDefault(pre,0)1);}returnans;}}239. 滑动窗口最大值239. 滑动窗口最大值单调队列单调队列套路右边入元素进入队尾同时维护队列单调性左边出元素离开队首记录/维护答案根据队首单调队列的巧妙之处在于如果一个元素比后面进来的元素小那它永远不可能成为最大值可以直接淘汰维护队列的单调递减性质——队首永远是窗口内最大值classSolution{publicint[]maxSlidingWindow(int[]nums,intk){intnnums.length;int[]ansnewint[n-k1];// 窗口个数DequeIntegerqnewArrayDeque();// 更快的写法见【Java 数组】for(inti0;in;i){// 1. 右边入while(!q.isEmpty()nums[q.getLast()]nums[i]){q.removeLast();// 维护 q 的单调性}q.addLast(i);// 注意保存的是下标这样下面可以判断队首是否离开窗口// 2. 左边出intlefti-k1;// 窗口左端点if(q.getFirst()left){// 队首离开窗口q.removeFirst();}// 3. 在窗口左端点处记录答案if(left0){// 由于队首到队尾单调递减所以窗口最大值就在队首ans[left]nums[q.getFirst()];}}returnans;}}Deque 的方法分三组功能相同但行为不同队尾操作当队列用表格方法抛异常返回特殊值添加元素addLast(e)offerLast(e)移除元素removeLast()pollLast()查看队尾getLast()peekLast()队首操作当队列用表格方法抛异常返回特殊值添加元素addFirst(e)offerFirst(e)移除元素removeFirst()pollFirst()查看队首getFirst()peekFirst()栈操作当栈用表格方法说明push(e)入栈等价于 addFirstpop()出栈等价于 removeFirstpeek()查看栈顶等价于 peekFirst76. 最小覆盖子串76. 最小覆盖子串核心就是右端点扩大窗口找可行解左端点收缩窗口找最优解右指针不断右移扩大窗口一旦窗口涵盖 t 的所有字符左指针就开始右移收缩窗口每次收缩前记录最短答案直到窗口不再满足条件然后右指针继续扩张如此反复直到遍历完整个字符串A D O B E C O D E B A N C 0 1 2 3 4 5 6 7 8 9 ... right0~5: 窗口 [A D O B E C]包含 A,B,C → 涵盖 → 开始收缩 left left0: [A D O B E C] 涵盖长度6记录 left1: [D O B E C] 涵盖长度5记录 left2: [O B E C] 不涵盖缺A停止收缩 right6~9: 继续右移窗口扩大 → 再次涵盖时收缩 left... right12: 最终找到 [B A N C]长度4最短classSolution{publicStringminWindow(StringS,Stringt){int[]cntSnewint[128];// s 子串字母的出现次数int[]cntTnewint[128];// t 中字母的出现次数for(charc:t.toCharArray()){cntT[c];}char[]sS.toCharArray();intms.length;intansLeft-1;intansRightm;intleft0;for(intright0;rightm;right){// 移动子串右端点cntS[s[right]];// 右端点字母移入子串 如果 s[right] 是一个 char 类型的字符它会被自动转换成对应的 ASCII/Unicode 数值int然后作为数组下标使用while(isCovered(cntS,cntT)){// 涵盖if(right-leftansRight-ansLeft){// 找到更短的子串ansLeftleft;// 记录此时的左右端点ansRightright;}cntS[s[left]]--;// 左端点字母移出子串left;}}returnansLeft0?:S.substring(ansLeft,ansRight1);//substring 方法是左闭右开的}privatebooleanisCovered(int[]cntS,int[]cntT){for(intiA;iZ;i){if(cntS[i]cntT[i]){returnfalse;}}for(intia;iz;i){if(cntS[i]cntT[i]){returnfalse;}}returntrue;}}