leetcode76 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路：双指针，两个指针中间代表一个字符串。

都往右边走，满足条件就左指针向右（缩），不满足条件就右指针向右（扩）

  

   

    

     

    
    

     

      public String minWindow(String s, String t) {
     
    
   

    

     

    
    

     
 int[] map = new int[128];
     
    
   

    

     

    
    

     
 // 遍历字符串 t，初始化每个字母的次数
     
    
   

    

     

    
    

     
 for (int i = 0; i < t.length(); i++) {
     
    
   

    

     

    
    

     
 char char_i = t.charAt(i);
     
    
   

    

     

    
    

     

       map[char_i]++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int left = 0; // 左指针
     
    
   

    

     

    
    

     
 int right = 0; // 右指针
     
    
   

    

     

    
    

     
 int ans_left = 0; // 保存最小窗口的左边界
     
    
   

    

     

    
    

     
 int ans_right = -1; // 保存最小窗口的右边界
     
    
   

    

     

    
    

     
 int ans_len = Integer.MAX_VALUE; // 当前最小窗口的长度
     
    
   

    

     

    
    

     
 int count = t.length();
     
    
   

    

     

    
    

     
 // 遍历字符串 s
     
    
   

    

     

    
    

     
 while (right < s.length()) {
     
    
   

    

     

    
    

     
 char char_right = s.charAt(right);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 // 当前的字母次数减一
     
    
   

    

     

    
    

     

       map[char_right]--;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //代表当前符合了一个字母
     
    
   

    

     

    
    

     
 if (map[char_right] >= 0) {
     
    
   

    

     

    
    

     

       count--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 // 开始移动左指针，减小窗口
     
    
   

    

     

    
    

     
 while (count == 0) { // 如果当前窗口包含所有字母，就进入循环
     
    
   

    

     

    
    

     
 // 当前窗口大小
     
    
   

    

     

    
    

     
 int temp_len = right - left + 1;
     
    
   

    

     

    
    

     
 // 如果当前窗口更小，则更新相应变量
     
    
   

    

     

    
    

     
 if (temp_len < ans_len) {
     
    
   

    

     

    
    

     

       ans_left = left;
     
    
   

    

     

    
    

     

       ans_right = right;
     
    
   

    

     

    
    

     

       ans_len = temp_len;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 // 得到左指针的字母
     
    
   

    

     

    
    

     
 char key = s.charAt(left);
     
    
   

    

     

    
    

     
 // 因为要把当前字母移除，所有相应次数要加 1
     
    
   

    

     

    
    

     

       map[key]++;
     
    
   

    

     

    
    

     
 //此时的 map[key] 大于 0 了，表示缺少当前字母了，count++
     
    
   

    

     

    
    

     
 if (map[key] > 0) {
     
    
   

    

     

    
    

     

       count++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       left++; // 左指针右移
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 // 右指针右移扩大窗口
     
    
   

    

     

    
    

     

       right++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return s.substring(ans_left, ans_right + 1);
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103418798