和为K的子数组(560)
先看代码- class Solution {
- public int subarraySum(int[] nums, int k) {
- int res = 0;
- int preSum = 0;
- Map<Integer, Integer> cnt = new HashMap<>(nums.length);
- for (int num : nums){
- cnt.merge(preSum, 1, Integer::sum);
- preSum += num;
- res += cnt.getOrDefault(**preSum - k**, 0);
- }
- return res;
- }
- }
一次循环一边更新相同前缀和的前缀数量, 一边将吻合的数据放入res
preSum - k 是前缀和的关键
<img alt="image.png" loading="lazy">
只有”单调”的数据集才得当用滑动窗口, 非”单调”的前缀和才好做 , 否则每次移动窗口都带来混乱
“单调”指的是 任意 num>0且单调递增 OR 任意 num < 0 且单调递减
不符合单调
符合单调
滑动窗口最大值(560)
先看代码- class Solution {
- public int[] maxSlidingWindow(int[] nums, int k) {
- int n = nums.length;
- int[] res = new int[n-k+1];
- Deque<Integer> queue = new ArrayDeque<>();
- for (int i = 0; i < n; i++){
- while (!queue.isEmpty() && nums[queue.getLast()] <= nums[i]){
- queue.removeLast();
- }
- queue.addLast(i);
- if (i-k >= queue.getFirst()){
- queue.removeFirst();
- }
- if(i-k+1 >= 0) res[i-k+1] = nums[queue.getFirst()];
- }
- return res;
- }
- }
队列中存储数据下标
很多题目都是通过存储下标 因为一个下标含有两个有效数据 → </strong>
最小覆盖字串(076)
先看代码- class Solution {
- public String minWindow(String s, String t) {
- int needCnt = 0;
- int[] need = new int[128];
- for (char c : t.toCharArray()){
- if (need[c] == 0){
- needCnt++;
- }need[c]++;
- }
- int n = s.length();
- int resLef = -1;
- int resRig = n;
- int lef = 0;
- for (int rig = 0; rig < n; rig++){
- char cR = s.charAt(rig);
- need[cR]--;
- if (need[cR] == 0){
- needCnt--;
- }
- while (needCnt == 0){
- if(resRig-resLef > rig-lef){
- resLef = lef;
- resRig = rig;
- }
- char cL = s.charAt(lef);
- if (need[cL] == 0) needCnt++;
- need[cL]++;
- lef++;
- }
- }
- return resLef < 0 ? "" : s.substring(resLef, resRig+1);
- }
- }
通过数组need存储需要各种类字符数量, needCnt 存储需要的字符种类
施工中…
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
| 
