f Java-hot100之子串 - Powered by qidao123.com技术社区

hot100之子串

打印 上一主题 下一主题

主题 1837|帖子 1837|积分 5511

和为K的子数组(560)

先看代码
  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         int res = 0;
  4.         int preSum = 0;
  5.         Map<Integer, Integer> cnt = new HashMap<>(nums.length);
  6.         for (int num : nums){
  7.             cnt.merge(preSum, 1, Integer::sum);
  8.             preSum += num;
  9.             res += cnt.getOrDefault(**preSum - k**, 0);
  10.         }
  11.         return res;
  12.     }
  13. }
复制代码

  • 分析
cnt用来记录相同前缀和的前缀数量
一次循环一边更新相同前缀和的前缀数量, 一边将吻合的数据放入res
preSum - k 是前缀和的关键
<img alt="image.png" loading="lazy">


  • 感悟
只有”单调”的数据集才得当用滑动窗口, 非”单调”的前缀和才好做 , 否则每次移动窗口都带来混乱
“单调”指的是 任意 num>0且单调递增 OR 任意 num < 0 且单调递减

不符合单调

符合单调
滑动窗口最大值(560)

先看代码
  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  3.         int n = nums.length;
  4.         int[] res = new int[n-k+1];
  5.         Deque<Integer> queue = new ArrayDeque<>();
  6.         for (int i = 0; i < n; i++){
  7.             while (!queue.isEmpty() && nums[queue.getLast()] <= nums[i]){
  8.                 queue.removeLast();
  9.             }
  10.             queue.addLast(i);
  11.             if (i-k >= queue.getFirst()){
  12.                 queue.removeFirst();
  13.             }
  14.             if(i-k+1 >= 0) res[i-k+1] = nums[queue.getFirst()];
  15.         }
  16.         return res;
  17.     }
  18. }
复制代码

  • 分析
通过维护单调递减队列queue
队列中存储数据下标

  • 感悟
很多题目都是通过存储下标 因为一个下标含有两个有效数据 → </strong>
最小覆盖字串(076)

先看代码
  1. class Solution {
  2.     public String minWindow(String s, String t) {
  3.         int needCnt = 0;
  4.         int[] need = new int[128];
  5.         for (char c : t.toCharArray()){
  6.             if (need[c] == 0){
  7.                 needCnt++;
  8.             }need[c]++;
  9.         }
  10.         int n = s.length();
  11.         int resLef = -1;
  12.         int resRig = n;
  13.         int lef = 0;
  14.         for (int rig = 0; rig < n; rig++){
  15.             char cR = s.charAt(rig);
  16.             need[cR]--;
  17.             if (need[cR] == 0){
  18.                 needCnt--;
  19.             }
  20.             while (needCnt == 0){
  21.                 if(resRig-resLef > rig-lef){
  22.                     resLef = lef;
  23.                     resRig = rig;
  24.                 }
  25.                 char cL = s.charAt(lef);
  26.                 if (need[cL] == 0) needCnt++;
  27.                 need[cL]++;
  28.                 lef++;
  29.             }
  30.         }
  31.         return resLef < 0 ? "" : s.substring(resLef, resRig+1);
  32.     }
  33. }
复制代码

  • 分析
通过滑动窗口遍历
通过数组need存储需要各种类字符数量, needCnt 存储需要的字符种类

  • 感悟
施工中…

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
继续阅读请点击广告

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

用户国营

论坛元老
这个人很懒什么都没写!
快速回复 返回顶部 返回列表