企业官网建设流程全解析

子串专题

560. 和为 K 的子数组

560. 和为 K 的子数组

暴力

遍历得到所有子串并求和 筛选出符合条件的

classSolution{publicintsubarraySum(int[]nums,intk){intans=0;intn=nums.length;for(inti=0;i<n;i++){//列举每个元素当子串结尾的情况intsum=0;for(intj=i;j>=0;j--){//求所有以这个子串为结尾的和sum+=nums[j];if(sum==k)ans++;}}returnans;}}

前缀和+哈希表

前缀和：pre[i]=pre[i−1]+nums[i]

[j…i] 这个子数组和为 k这个条件我们可以转化为pre[i]−pre[j−1]==k

简单移项可得符合条件的下标 j 需要满足

pre[j−1]==pre[i]−k

classSolution{publicintsubarraySum(int[]nums,intk){intans=0,pre=0;intn=nums.length;HashMap<Integer,Integer>mp=newHashMap<>();// 记录前缀和及其出现次数mp.put(0,1);// 前缀和为0的有一个for(inti=0;i<n;i++){pre+=nums[i];if(mp.containsKey(pre-k)){ans+=mp.get(pre-k);}mp.put(pre,mp.getOrDefault(pre,0)+1);}returnans;}}

239. 滑动窗口最大值

239. 滑动窗口最大值

单调队列

单调队列套路

1. 右边入（元素进入队尾，同时维护队列单调性）
2. 左边出（元素离开队首）
3. 记录/维护答案（根据队首）

单调队列的巧妙之处在于：如果一个元素比后面进来的元素小，那它永远不可能成为最大值，可以直接淘汰

维护队列的单调递减性质——队首永远是窗口内最大值

classSolution{publicint[]maxSlidingWindow(int[]nums,intk){intn=nums.length;int[]ans=newint[n-k+1];// 窗口个数Deque<Integer>q=newArrayDeque<>();// 更快的写法见【Java 数组】for(inti=0;i<n;i++){// 1. 右边入while(!q.isEmpty()&&nums[q.getLast()]<=nums[i]){q.removeLast();// 维护 q 的单调性}q.addLast(i);// 注意保存的是下标，这样下面可以判断队首是否离开窗口// 2. 左边出intleft=i-k+1;// 窗口左端点if(q.getFirst()<left){// 队首离开窗口q.removeFirst();}// 3. 在窗口左端点处记录答案if(left>=0){// 由于队首到队尾单调递减，所以窗口最大值就在队首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)	入栈（等价于 addFirst）
pop()	出栈（等价于 removeFirst）
peek()	查看栈顶（等价于 peekFirst）

76. 最小覆盖子串

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 ... right=0~5: 窗口 [A D O B E C]，包含 A,B,C → 涵盖！ → 开始收缩 left： left=0: [A D O B E C] 涵盖，长度6，记录 left=1: [D O B E C] 涵盖，长度5，记录 left=2: [O B E C] 不涵盖（缺A），停止收缩 right=6~9: 继续右移，窗口扩大 → 再次涵盖时，收缩 left... right=12: 最终找到 [B A N C]，长度4，最短

classSolution{publicStringminWindow(StringS,Stringt){int[]cntS=newint[128];// s 子串字母的出现次数int[]cntT=newint[128];// t 中字母的出现次数for(charc:t.toCharArray()){cntT[c]++;}char[]s=S.toCharArray();intm=s.length;intansLeft=-1;intansRight=m;intleft=0;for(intright=0;right<m;right++){// 移动子串右端点cntS[s[right]]++;// 右端点字母移入子串 如果 s[right] 是一个 char 类型的字符，它会被自动转换成对应的 ASCII/Unicode 数值（int），然后作为数组下标使用while(isCovered(cntS,cntT)){// 涵盖if(right-left<ansRight-ansLeft){// 找到更短的子串ansLeft=left;// 记录此时的左右端点ansRight=right;}cntS[s[left]]--;// 左端点字母移出子串left++;}}returnansLeft<0?"":S.substring(ansLeft,ansRight+1);//substring 方法是"左闭右开"的}privatebooleanisCovered(int[]cntS,int[]cntT){for(inti='A';i<='Z';i++){if(cntS[i]<cntT[i]){returnfalse;}}for(inti='a';i<='z';i++){if(cntS[i]<cntT[i]){returnfalse;}}returntrue;}}