区块链技术博客
www.b2bchain.cn

76. 最小覆盖子串 滑动窗口

这篇文章主要介绍了76. 最小覆盖子串 滑动窗口,通过具体代码讲解8113并且分析了76. 最小覆盖子串 滑动窗口的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了76. 最小覆盖子串 滑动窗口。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8113.html。具体如下:

76. 最小覆盖子串 

 class Solution {    public static String minWindow(String s, String t) {         if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {             return "";         }         //用来统计t中每个字符出现次数         int[] needs = new int[128];         //用来统计滑动窗口中每个字符出现次数         int[] window = new int[128];          for (int i = 0; i < t.length(); i++) {             needs[t.charAt(i)]++;         }          int left = 0;         int right = 0;          String res = "";          //目前有多少个字符         int count = 0;          //用来记录最短需要多少个字符。         int minLength = s.length() + 1;         //首先求出可行解 移动右边指针         while (right < s.length()) {             char ch = s.charAt(right);             window[ch]++;             //当前所需 字符 比已有的大 说明此时遍历到t中拥有的字符             if (needs[ch] > 0 && needs[ch] >= window[ch]) {                 count++;             }              //一直移动左指针 到不满足条件为止              while (count == t.length()) {                 ch = s.charAt(left);                 //遍历到t中拥有的字符时候,count--                 if (needs[ch] > 0 && needs[ch] >= window[ch]) {                     count--;                 }                 //更新最短值                 if (right - left + 1 < minLength) {                     minLength = right - left + 1;                     res = s.substring(left, right + 1);                 }                 //移动左窗口                 window[ch]--;                 left++;              }                          right++;          }         return res;     }    }

 

本文地址https://www.b2bchain.cn/8113.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 76. 最小覆盖子串 滑动窗口
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们