力扣 hot100 最小覆盖子串 滑动窗口 字符计数

👨‍🏫 题目地址

🍻 AC code

class Solution {
    public String minWindow(String s, String t)
	{
		int n = s.length();
		int m = t.length();
		if (n < m)
			return "";

		char[] tt = t.toCharArray();
		int[] cnt = new int[128];// 字符计数数组
		for (int i = 0; i < m; i++)
			cnt[tt[i]]++;// 统计t串的字符

		int l = 0, r = 0;
		int left = 0, right = 0, ans = Integer.MAX_VALUE;
		while (r < n)
		{
			System.out.println(m);
			char c = s.charAt(r++);
			if (cnt[c] > 0)// 在 t串 中出现过的字符才减，减到 0 即止
				m--;
			cnt[c]--;// 当前子串 抵消 t串 的字符统计
			while (m == 0)// 当前子串完全覆盖完 t 串
			{
				if (r - l < ans)// 更新答案
				{
					ans = r - l;
					left = l;
					right = r;
				}
				c = s.charAt(l++);// 子串左边界右移
				// cnt[c] == 0 : 字符c是 t 串的。如果不是t串的，cnt[c] 为负值
				if (cnt[c] == 0)
					m++;
				cnt[c]++;// 取消对当前字符的统计
			}
		}
		if (ans == Integer.MAX_VALUE)
			return "";
		else
			return s.substring(left, right);
	}
}
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

👨‍🏫 参考题解