当前位置：首页 > ds >正文

【滑动窗口+哈希表/数组记录】Leetcode 76. 最小覆盖子串

ds 2025/5/9 4:46:24

题目要求

给定两个字符串 s 和 t，找到 s 中涵盖 t 所有字符的最小子串。如果不存在，则返回空字符串。

示例1

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含 t 中的 'A'、'B' 和 'C'。

示例2

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例3

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，没有符合条件的子字符串。

实际应用

寻找字符串 s 中涵盖字符串 t 所有字符的最短子串的问题。

文本处理领域

场景：在文本编辑器中，用户想要快速找到包含特定关键词或短语的最小文本范围。

例子：假设你正在处理一个大型文档，想要找到包含 error 和 warning 的最小段落。使用滑动窗口算法，可以快速定位到包含这两个词的最短文本范围，从而提高信息检索的效率。

数据流处理领域

场景：在实时数据监控系统中，需要识别包含特定特征的最短数据片段。

例子：在网络流量监控中，系统需要实时分析数据包，以识别包含特定攻击特征（如 SYN 和ACK 标志位）的最短数据片段。滑动窗口算法可以帮助快速找到这些特征，从而及时采取措施防止潜在的网络攻击。

滑动窗口法

思想

滑动窗口法通过维护一个左右指针表示的窗口，在字符串 s 上滑动。

右指针不断右移扩大窗口，直到窗口内包含 t 中的所有字符。

随后，左指针右移缩小窗口，寻找满足条件的最短子串。

期间用数组或哈希表记录字符频率，判断窗口是否符合要求。

该算法的优势在于它能够将嵌套循环问题优化为线性时间复杂度问题，在处理大数据时效率显著。

哈希表记录字符频率

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;string minWindow(string s, string t)
{unordered_map<char, int> need, window;for (char c : t)need[c]++;int left = 0, right = 0;// 记录当前窗口中满足条件的字符种类数int valid = 0;// 记录最小覆盖子串的起始索引及长度int start = 0, length = INT_MAX;while (right < s.size()){// c 是将移入窗口的字符char c = s[right];// 右移窗口，right指向窗口的下一个位置right++;// 进行窗口内数据的一系列更新if (need.count(c)){window[c]++;if (window[c] == need[c])valid++;}// 判断左侧窗口是否要收缩while (valid == need.size()){// 在这里更新最小覆盖子串if (right - left < length){start = left;length = right - left;}// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新if (need.count(d)){if (window[d] == need[d])valid--;window[d]--;}}}// 返回最小覆盖子串return length == INT_MAX ? "" : s.substr(start, length);
}int main()
{string s = "ADOBECODEBANC";string t = "ABC";cout << minWindow(s, t) << endl;return 0;
}

数组记录字符频率

数组代替哈希表记录字符频率可以提升访问速度，因为字符范围有限，数组索引对应字符，访问时间固定。但数组难以直接确定不重复的元素个数，所以用 valid 记录符合 need 条件的字符种类数，确保窗口中字符及其数量满足要求。

#include <iostream>
#include <string>
#include <vector>
using namespace std;string minWindow(string s, string t)
{vector<int> need(128, 0);vector<int> window(128, 0);for (char c : t)need[c]++;int left = 0, right = 0;// 记录窗口中满足need条件的字符个数int valid = 0;// 记录最小覆盖子串的起始索引及长度int start = 0, length = INT_MAX;while (right < s.size()){// c 是将移入窗口的字符char c = s[right];// 右移窗口，right指向窗口的下一个位置right++;// 进行窗口内数据的一系列更新if (need[c]){window[c]++;if (window[c] <= need[c])valid++;}// 判断左侧窗口是否要收缩while (valid == t.size()){// 在这里更新最小覆盖子串if (right - left < length){start = left;length = right - left;}// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新if (need[d]){if (window[d] == need[d])valid--;window[d]--;}}}// 返回最小覆盖子串return length == INT_MAX ? "" : s.substr(start, length);
}
int main()
{string s = "ADOBECODEBANC";string t = "ABC";cout << minWindow(s, t) << endl;return 0;
}

时间复杂度

通常为 O(m + n)，其中 m 和 n 分别是字符串 s 和 t 的长度。