【算法】滑动窗口
in 博客目录
本文记录了近期在leetcode上刷到的关于滑动窗口的题目。
滑动窗口其实也可以归类为双指针的一种。滑动窗口的基本思想是维护一个窗口，窗口内的元素满足某些条件。窗口的左右边界分别用两个指针表示，窗口的大小可以变化。
解题通用模板：
//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
//当前考虑的元素
while (l <= r && check()) {//区间[left,right]不符合题意
//扩展左边界
}
//区间[left,right]符合题意，统计相关信息
}
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104
进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
暴力解法
暴力解法的思路是枚举所有可能的子数组，计算子数组的和是否大于等于target。如果是，更新最小长度。
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
// 枚举子数组的左边界
for (int i = 0; i < n; i++) {
int sum = 0;
// 枚举子数组的右边界
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum >= s) {
ans = Math.min(ans, j - i + 1);
break;
}
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
复杂度分析
- 时间复杂度：O(n2)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。
- 空间复杂度：O(1)。
滑动窗口
滑动窗口的思路是维护一个窗口，窗口的左右边界分别用两个指针表示，窗口的大小可以变化。
初始时，窗口的左右边界都指向数组的第一个元素，sum和设为0。
- 每次将右指针右移一位，将右指针指向的元素加入sum中。
- 如果sum大于等于target，说明满足条件了，更新最小长度，同时将左指针右移一位，将左指针指向的元素从sum中减去。
- 重复以上步骤，直到右指针到达数组的末尾。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
// 因为要找最小值，result设为 INT_MAX 最大值，方便后续比较
int result = INT_MAX;
int left = 0;
int right = 0;
int sum = 0;
// 右指针右移，加入元素
while (right <= n - 1) {
sum += nums[right];
// 可以不用判断左右指针相对位置，重合时，减完sum就为0了
while (sum >= s) {
result = min(right - left + 1, result);
// 左指针右移，提前减去这个位置的元素
sum -= nums[left];
left++;
}
right++;
}
// 如果result没有被更新，说明没有符合条件的子数组
return result == INT_MAX ? 0 : result;
}
};
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
滑动窗口加unordered_set记录
我们不妨以示例一中的字符串 abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：
以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb；
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b；
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b；
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。
可以看到，随着左指针移动，右边界也是在移动的。
我们就可以使用「滑动窗口」来解决这个问题了：
我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」。
在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
在枚举结束后，我们找到的最长的子串的长度即为答案。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if (n <= 1) {
return n;
}
int ans = 0;
unordered_set<char> filter;
int right = 0;
for (int left = 0; left < n; left++) {
// 左指针向右移动一格，移除掉遍历检查过的字符
if (left != 0) {
// 移除掉遍历检查过的字符
filter.erase(s[left - 1]);
}
// 右指针向右移动，加入元素，直到遇到重复元素
while (right <= n - 1 && !filter.count(s[right])) {
filter.insert(s[right]);
right++;
}
// 更新答案，此时右指针指向的元素是重复元素，所以 right - left 是当前窗口的长度
ans = max(ans, right - left);
}
return ans;
}
};
438.找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
思路 滑动窗口检查异位词
根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；
不需要费劲去排列组合，只需要看每种字符的数量是否相等即可。
当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。
而且字符的存储形式是一个整形，所以我们可以用一个 vector<int> 来记录窗口中每种字母的数量。
两个 vector<int> 分别记录字符串 p 中每种字母的数量和窗口中每种字母的数量。数组相等可以直接使用 == 运算符。底层已经实现了。
vector的==运算符，内部已实现，先判断长度，若长度相同再逐个比较元素是否相等。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sSize = s.size();
int pSize = p.size();
if (sSize < pSize) {
return {};
}
vector<int> result;
// 承载s和p中每一个字符的数组，大小固定为26
vector<int> sDict(26);
vector<int> pDict(26);
for (int i = 0; i < pSize; i++) {
// 填入字母和字符a的差值作为存储判断的数据
sDict[s[i] - 'a']++;
pDict[p[i] - 'a']++;
}
// 至此，p字符串的结构体已经录入了pDict这个数组
// 先比较一次s的开头字符串
if (sDict == pDict) {
result.emplace_back(0);
}
// 比较剩余的元素
for (int i = 0; i < sSize - pSize; i++) {
// 补上新的剩余字符计入
sDict[s[pSize + i] - 'a']++;
// 删掉之前计算的字符，保持窗口大小不变
sDict[s[i] - 'a']--;
if (sDict == pDict) {
// i 是从减去p长度的后一个位置开始的，在s中的实际下标需要加 1
result.emplace_back(i + 1);
}
}
return result;
}
};
emplace_back是 vector 的一个成员函数，用于在 vector 的末尾直接构造一个元素，而不是先创建一个临时对象再将其复制到 vector 中。适合大对象，复杂对象的构造。这里使用push_back也没差。
30.串联所有单词的子串
这题可以说是438的进阶版，不过一个是字符，一个是字符串版本。
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示：
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成
滑动窗口检查
使用的还是滑动窗口检查异位词这题的思想。只不过检查的对象成了字符串，并且用来比较的数据集合改用hash表，记录每个字符串出现的次数。
重点在于如何划分窗口。记 words 的长度为 m ，words 中每个单词的长度为 n ， s 的长度为 ls 。首先需要将 s 划分为单词组，每个单词的大小均为 n （首尾除外）。这样的划分方法有 n 种，即先删去前 i （i=0∼n−1） 个字母后，将剩下的字母进行划分，如果末尾有不到 n 个字母也删去。对这 n 种划分得到的单词数组分别使用滑动窗口对 words 进行类似于字母异位词的搜寻。
检查流程如下：
第一次滑动流程
初始窗口 ['bar', 'foo','foo'] 未命中
入'bar'出'bar' ['foo','foo','bar'] 未命中
入'the'出'foo' ['foo','bar', 'the'] 命中 index 6
入'foo'出'foo' ['bar','the', 'foo'] 命中 index 9
入'bar'出'bar' ['the','foo','bar'] 命中index 12
入'man'出'the' ['foo','bar','man'] 未命中
结束
第二次滑动流程
初始窗口 ['arf','oof','oob'] 未命中
划动过程略
第三次滑动流程
初始窗口 ['rfo','ofo','oba'] 未命中
划动过程略
class Solution {
public:
vector<int> findSubstring(string& s, vector<string>& words) {
vector<int> res; // 存储结果的向量，记录所有符合条件的起始索引
// 获取关键参数：
int m = words.size(); // words中单词的个数
int n = words[0].size(); // 每个单词的长度（题目保证所有单词长度相同）
int ls = s.size(); // 字符串s的长度
// 外层循环：从0到n-1，处理不同的起始偏移量
// 这样可以覆盖所有可能的对齐方式
// 第二个结束条件就是剩余的字符串长度不足以支持分割
for (int i = 0; i < n && i + m * n <= ls; ++i) {
// 使用哈希表记录当前窗口内各单词出现次数与words中次数的差异
unordered_map<string, int> differ;
// 初始化滑动窗口：截取从位置i开始的m个单词
for (int j = 0; j < m; ++j) {
// 从s中截取一个单词并加入differ（增加计数）
++differ[s.substr(i + j * n, n)];
}
// 用words中的单词来平衡differ（减少计数）
for (string& word : words) {
// 如果某个单词在words中，就在differ中减少其计数
if (--differ[word] == 0) {
// 如果计数减到0，就从differ中移除该单词
differ.erase(word);
}
}
// 开始逐词滑动窗口遍历
for (int start = i; start < ls - m * n + 1; start += n) {
// 初始窗口第一次检查已完成，如果不是初始窗口，需要更新differ
if (start != i) {
// 添加新进入窗口的单词（窗口右边界新增的单词）
string word = s.substr(start + (m - 1) * n, n);
if (++differ[word] == 0) {
differ.erase(word); // 如果计数变为0，移除
}
// 移除离开窗口的单词（窗口左边界移出的单词）
word = s.substr(start - n, n);
if (--differ[word] == 0) {
differ.erase(word); // 如果计数变为0，移除
}
}
// 检查当前窗口是否匹配：如果differ为空，说明窗口内的单词与words完全匹配
if (differ.empty()) {
res.emplace_back(start); // 记录当前起始位置
}
}
}
return res; // 返回所有找到的起始索引
}
};
76.最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
滑动窗口加哈希表动态判断
解题思路，右指针往前遍历，一路扩大检查的范围，直到当前窗口区域内，可以包含 t 字符串的组成字符数量后，再缩小范围，直到不包含，过程中动态更新区间大小，取最短区间。
本地验证OK，问题点是添加了一个hash表来判断对比，超出内存限制了。
class Solution {
public:
bool checkDict(unordered_map<char, int>& dyDict,
unordered_map<char, int>& tDict) {
auto it = tDict.begin();
while (it != tDict.end()) {
if (it->second > dyDict[it->first]) {
return false;
}
it++;
}
return true;
}
string minWindow(string s, string t) {
int n = s.size();
int m = t.size();
if (n < m) {
return "";
}
// 需要动态更新最小值
string result = "";
bool isFound = false;
unordered_map<char, int> tDict;
unordered_map<char, int> dynamicDitct;
// 先填入即将用来比对hash表数据
for (char c : t) {
tDict[c]++;
}
// 思路，一路扩大检查的范围，直到包含的tDict中的字符数量后，再缩小范围到不包含，记录下区间大小
int right = 0;
int left = 0;
while (right < n) {
dynamicDitct[s[right]]++;
// 包含了组成t的字符组合
while (left < n && left + m <= right + 1 &&
checkDict(dynamicDitct, tDict)) {
string temp = s.substr(left, right - left + 1);
if (result == "") {
result = temp;
} else {
result = result.size() > temp.size() ? temp : result;
}
dynamicDitct[s[left]]--;
left++;
}
right++;
}
return result;
}
};
优化内存消耗
内存问题有以下几点：
- 每次检查都要遍历整个 tDict ，在滑动窗口过程中被调用次数为 O(n²) 级别
- 每次调用
dyDict[it->first]可能会在 dyDict 中创建新键值对 - 频繁截取字符串，字符串可能很长，频繁创建和销毁消耗大量内存
优化思路：
- 使用两个计数器
required和formed来跟踪需要匹配的字符种类数和当前已匹配的字符种类数，避免每次都遍历整个 tDict
class Solution {
public:
string minWindow(string s, string t) {
if (s.empty() || t.empty() || s.length() < t.length()) return "";
unordered_map<char, int> tCount;
for (char c : t) tCount[c]++;
int required = tCount.size(); // 需要匹配的字符种类数
int formed = 0; // 当前已匹配的字符种类数
unordered_map<char, int> windowCount;
int left = 0, right = 0;
int minLen = INT_MAX;
int start = 0;
while (right < s.length()) {
char c = s[right];
windowCount[c]++;
// 检查当前字符是否达到t中的要求
if (tCount.count(c) && windowCount[c] == tCount[c]) {
formed++;
}
// 尝试收缩窗口
while (left <= right && formed == required) {
c = s[left];
// 更新最小窗口
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
// 移动左指针
windowCount[c]--;
if (tCount.count(c) && windowCount[c] < tCount[c]) {
formed--;
}
left++;
}
right++;
}
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}
};
官方题解
思路相同，性能更优：
class Solution {
public:
unordered_map<char, int> ori, cnt;
bool check() {
for (const auto& p : ori) {
if (cnt[p.first] < p.second) {
return false;
}
}
return true;
}
string minWindow(string s, string t) {
for (const auto& c : t) {
++ori[c];
}
int l = 0, r = -1;
int len = INT_MAX, ansL = -1, ansR = -1;
while (r < int(s.size())) {
if (ori.find(s[++r]) != ori.end()) {
++cnt[s[r]];
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
}
if (ori.find(s[l]) != ori.end()) {
--cnt[s[l]];
}
++l;
}
}
return ansL == -1 ? string() : s.substr(ansL, len);
}
};
