LeetCode 76. 最小覆盖子串

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 76. 最小覆盖子串

思路分析

滑动窗口问题

参考代码

func minWindow(s string, t string) string {
	// 记录 t 中每个字符的出现次数
	need := map[byte]int{}
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	window := map[byte]int{} // 记录当前窗口中的字符计数
	left, right := 0, 0
	valid := 0           // 记录有多少个字符满足 need 中的需求
	start := 0           // 最小覆盖子串的起始位置
	length := len(s) + 1 // 最小长度，初始为一个不可能的值

	for right < len(s) {
		c := s[right]
		right++ // 扩大窗口

		// 如果是需要的字符，则计入窗口中
		if _, ok := need[c]; ok {
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}

		// 当窗口已经包含 t 中所有字符时，尝试收缩窗口
		for valid == len(need) {
			// 更新最小覆盖子串的位置
			if right-left < length {
				start = left
				length = right - left
			}

			d := s[left]
			left++ // 收缩窗口

			if _, ok := need[d]; ok {
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}
		}
	}

	if length == len(s)+1 {
		return ""
	}
	return s[start : start+length]
}

时间复杂度：O(n + m)，其中 n 是字符串 s 的长度，m 是字符串 t 的长度。

空间复杂度：O(∣Σ∣)，其中 Σ 是字符集大小。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/78922337