hot100之子串

和为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;
 }
}
  • 分析

cnt用来记录相同前缀和的前缀数量

一次循环一边更新相同前缀和的前缀数量, 一边将吻合的数据放入res

preSum - k 是前缀和的关键

  • 感悟

只有”单调”的数据集才适合用滑动窗口, 非”单调”的前缀和才好做 , 否则每次移动窗口都带来混乱

“单调”指的是 任意 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;
 }
}
  • 分析

通过维护单调递减队列queue

队列中存储数据下标

  • 感悟

很多题目都是通过存储下标 因为一个下标含有两个有效数据 → <于数据集的位置, 数据的值>

最小覆盖字串(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 存储需要的字符种类

  • 感悟

施工中…

作者:crhl-yy原文地址:https://www.cnblogs.com/many-bucket/p/18913413

%s 个评论

要回复文章请先登录注册