时间轴

2025-11-14

init

题目：

P76 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-interview-150

滑动窗口：
window[left, right]，考虑下面问题：

  1. 当移动right时要更新哪些数据
  2. 什么情况下right要停止扩大，开始移动left缩小窗口
  3. 当移动left时要更新哪些数据
  4. 我们要的结果是在扩大窗口还是缩小窗口时进行更新？
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
#include <string>
#include <unordered_map>

using std::unordered_map;
using std::string;

class Solution {
    public:
	string minWindow(string s, string t)
	{
		unordered_map<char, int> need;
		unordered_map<char, int> window;
		for (char &ch : t) {
			need[ch]++;
		}
		int i = 0, j = 0, n = s.size();
		int start;
		int min_len = n + 1;
		int valid = 0;
		for (j = 0; j < n; j++) {
			if (!need.count(s[j])) {
				continue;
			}
			window[s[j]]++;

			if (window[s[j]] == need[s[j]]) {
				valid++;
			}
			while (valid == need.size()) { //收缩left
				if (j - i + 1 < min_len) {
					start = i;
					min_len = j - i + 1;
				}
				if (need.count(s[i])) {
					if (window[s[i]] == need[s[i]]) {
						valid--;
					}
					window[s[i]]--;
				}
				i++; // 左移窗口
			}
		}
		return min_len == n + 1 ? "" : s.substr(start, min_len);
	}
};