leetcode每日一题:76.最小覆盖子串

76.最小覆盖子串

img

img

代码和注释:

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
@Test 
   public void mainTest() {
       System.out.println(minWindow("ADOBECODEBANC", "ABC"));
   }

   // 滑动窗口
   public String minWindow(String s, String t) {
       if (s.length() == 0 || t.length() == 0) return "";
       int left = 0;// 左右指针
       int right = 0;
       // 存储s和t出现次数
       int[] snum = new int[128];
       int[] tnum = new int[128];
       int tlen = t.length();
       // t串存入
       for (int i = 0; i < tlen; i++) {
           tnum[t.charAt(i)]++;
       }

       int minLenth = s.length() + 1;
       int count = 0;
       int min = 0;
       int max = 0;
       while (right < s.length()) {// 右指针移动
           char ch = s.charAt(right);
           snum[ch]++;// 将s出现的次数存入数组
           // 如果满足 当前字符是t字符里的 并且在当前范围只出现一次
           if (tnum[ch] > 0 && tnum[ch] >= snum[ch]) {
               count++;
           }
           // 当长度满足t时
           while (count == tlen) {
               char c = s.charAt(left);
               // 从左到右移动left 指针直到count长度不足
               if (tnum[c] > 0 && tnum[c] >= snum[c]) {
                   count--;
               }
               // 找到最短长度 将初始和结尾储存
               if (right - left + 1 < minLenth) {
                   minLenth = right - left + 1;
                   min = left;
                   max = right + 1;
               }
               snum[c]--;
               left++;
           }
           right++;
       }
       return s.substring(min, max);
   }