滑动窗口
1.滑动窗口是左右指针的一种特殊的情况, 通常用于实现高效的字符串/数组内的满足某种条件的子串/连续子数组搜索, 比如计算一个字符串内的最小覆盖子串; 我们如果有两个字符串, s 和 t, 我们想在 s 中搜索满足符合 t 相关条件的情况, 如果不用滑动窗口的思想基本需要2次遍历: 需要对位置 i 为结尾进行遍历, 然后再内层再遍历一次匹配过程, 这样时间复杂度很高
2.这时候我们采用滑动窗口的思想, 维护右边和左边两个指针, 右边的指针负责不断向右边扩展直到满足某个条件, 满足条件之后这时候左右指针区间内的子串是完全满足 t 所需要的条件的, 此时虽然满足 t 条件, 但不一定是最优的, 所以我们尝试缩小左边界的指针, 去追逐滑动窗口内满足条件下的最优性, 直到打破这种最优性变成又不满足窗口条件的情况; 这时候再右指针继续拓展右边界, 直到满足窗口条件, 再缩小左边界, 如此周而复始直到整个字符串遍历完成
3.采用滑动窗口编码模板可以通用性地解决这一类的问题, 维护一个当前的窗口然后进行逻辑处理, 然后再移动窗口进行处理; 以字符串为例, 维护的是 s[left, right] 这个区间内的判断和处理逻辑: 滑动窗口是先控制窗口右边的边界先往右扩展, 将 s[right] 加入到窗口, 然后在判断左边的边界是否有收缩的可能, 如果可能则将 s[left] 移除窗口, 伪代码如下所示
4.通常情况下, 我们处理窗口内的判断和处理逻辑时, 可能需要灵活引入哈希表等辅助结构辅助我们高效判断条件是否满足, 例如一种比较常用的情况下是
(i). window: 当前我们的窗口内满足的情况
(ii). need: 辅助用来计数我们需要达到处理窗口的条件, 通过比较当前的 window 和 need 的情况, 然后可决策是否满足题意要求, 或者决策窗口是否左侧收缩
5.滑动窗口在初始化时, 通常是left = right = 0, 且将窗口区间设计成左闭右开 [left, right) 这样的一个结构, 为什么设计成左闭右开? 是因为如果选择两边都闭 [left, right], 那么还没开始移动的时候区间里面就有1个元素; 如果设计成两边都开 (left, right), 那么即使向右移动一位窗口还是没有元素; 这两种都不好处理, 最好处理的情况是左闭右开 [left, right), 达到的效果是还没有移动的时候, 区间没有元素, 向右移动1个单位, 那么就加入一个元素到窗口
int l = 0;
int r = 0;
int len = s.size();
while (r < len) {
// s[r] 加入到窗口
++r; // 右边界移动
// 窗口内统计数据更新
// 窗口内统计数据更新完之后, 可能就能满足窗口条件
while (window need shrink) {
// s[l] 移除窗口
++l; // 左边界移动
// 窗口内统计数据更新
// 窗口内统计数据更新完之后, 可能就会不满足窗口条件了, 就会跳出这里的 while (), 右边界持续探索
}
}
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 的子串中，因此没有符合条件的子字符串，返回空字符串。
分析:
1.我们用滑动窗口处理这个最小覆盖子串的搜索问题, 初始化左右指针 left/right 都是起始位置, 对于判定子串是否覆盖, 我们先建立一个 unordered_map
2.因为我们需要记录下来最小的覆盖子串的字符串, 最简单的方法是记录下来满足条件的时候的位置, 以及是当前覆盖子串长度; 然后不断更新这个长度
3.我们再理一下思路: 先对 t 字符扫描进 need 统计需要的情况; 左右指针从 0 处初始化, 右边指针持续向右扫, 如果存在在当前的字符里面, 满足在 need 中需要, 那么就对 window[rc] += 1, 然后再判断是否满足覆盖的条件, valid == need.size(), 如果满足那么就尝试更新长度, 并且判断左边界缩减, 左边界缩减的条件是什么? 左指针所在的字符是需要的字符中的, —valid, 且窗口中 —window[lc]
class Solution {
public:
string minWindow(string s, string t) {
int l = 0;
int r = 0;
unordered_map<char, int> need;
unordered_map<char, int> window;
for (auto c: t) {
++need[c];
}
int valid = 0; // valid 记录有多少个独立的字符是满足计数条件的
int len = s.size();
int ansStart = 0;
int ansLen = s.size() + 1; // 初始化默认按照最长长度 + 1来
while (r < len) {
char rc = s[r];
++r;
if (need.count(rc)) {
++window[rc];
if (window[rc] == need[rc]) {
++valid;
}
}
while (valid == need.size()) {
if (r - l < ansLen) {
ansStart = l;
ansLen = r - l;
}
char lc = s[l];
++l;
if (need.count(lc)) {
if (window[lc] == need[lc]) {
--valid;
}
--window[lc];
}
}
}
return ansLen == s.size() + 1 ? "" : s.substr(ansStart, ansLen);
}
};
567.字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。示例 1：输入：s1 = “ab” s2 = “eidbaooo” 输出：true 解释：s2 包含 s1 的排列之一 (“ba”).
示例 2：输入：s1 = “ab” s2 = “eidboaoo” 输出：false
分析:
1.问题是要判断排列, 那么问题转化成是否包含一个子串, 包含 s1 中全部的字符且不包含其他的字符
2.搜索的空间是 [l, r), 左闭右开的区间
3.用 valid 去保存有多少个字符满足了恰好包含的需求, 判断包含的条件是 valid == need.size()
4.当 right 往右扩张的时候, 取出来当前字符 s[r], 如果 need[rc] > 0的时候, 窗口里面 window[rc]+=1 ; 同时需要判断当前是否有某个字符满足了统计要求 need[rc] == window[rc], 那么累计一个 valid
5.left 边界发生缩小的条件是, r-l >= s1.size()
6.当 left 发生边界缩减, 取出来当前的字符 s[l], 如果 need[lc] > 0的时候, 先判断当前是否满足统计要求 need[lc] == window[lc], 如果是的话 valid 还原, 同时将字符从window里面去除出去
7.这里进入窗口和边界缩减有个不同, 进入窗口的时候是先得让 window 进来, 然后再判断; 边界缩减的时候需要先去判断满足统计要求, 再去移除窗口—window[lc]
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int l = 0;
int r = 0;
unordered_map<char, int> need;
unordered_map<char, int> window;
int s1Len = s1.size();
int s2Len = s2.size();
int valid = 0;
for (char c: s1) {
++need[c];
}
while (r < s2Len) {
char rc = s2[r];
++r;
if (need.count(rc)) {
++window[rc];
if (need[rc] == window[rc]) {
++valid;
}
}
while (r - l >= s1Len) {
if (valid == need.size()) {
return true;
}
char lc = s2[l];
++l;
if (need.count(lc)) {
if (need[lc] == window[lc]) {
--valid;
}
--window[lc];
}
}
}
return false;
}
};
看了 leetcode 官方的解法, 感觉代码更优雅更容易理解一些, 直接用 vector
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int lenS1 = s1.size();
int lenS2 = s2.size();
if (lenS1 > lenS2) {
return false;
}
vector<int> cntS1(26, 0);
vector<int> cntS2(26, 0);
// s1 统计次数, 同时 s2 遍历第一个窗口
for (int i = 0; i < lenS1; ++i) {
cntS1[s1[i] - 'a'] += 1;
cntS2[s2[i] - 'a'] += 1;
}
if (cntS1 == cntS2) {
return true;
}
for (int i = 1; i < lenS2 - lenS1 + 1; ++i) {
cntS2[s2[i-1] - 'a'] -= 1; // 左边滑动1个窗口
cntS2[s2[i + lenS1 - 1] - 'a'] += 1; // 右边滑动1个窗口
if (cntS1 == cntS2) {
return true;
}
}
return false;
}
};
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.先采用模板的方法: 用滑动窗口搜索每个窗口内是否每个字母出现的次数和需要的次数是一致的; 首先构建一个 hash table 将需要的次数统计一下
2.开始滑动, 每次滑动的时候记录一下当前窗口内每个字符出现的次数, 如何判定所有的次数和整体的次数相等? 一种简单的方法是再引入一个窗口内满足条件的总次数, 每次判定当前右边指针指向的那个字符和我们想要的这个字符出现次数是匹配的情况下, ++valid, 如果 validCnt = p.size(); 那么就推出去结果
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> need;
unordered_map<char, int> window;
for (char c: p)
++need[c];
int left = 0;
int right = 0;
int valid = 0;
vector<int> ans;
while (right < s.size()) {
char r = s[right];
++right;
if (need.count(r)) {
++window[r];
if (need[r] == window[r])
++valid;
}
while (right - left >= p.size()) {
if (valid == need.size()) {
ans.push_back(left);
}
char l = s[left];
++left;
if (need.count(l)) {
if (need[l] == window[l]) {
--valid;
}
--window[l];
}
}
}
return ans;
}
};
滑动窗口的方法可以采用更简单的方式, 用 vector
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size();
int pLen = p.size();
vector<int> ans;
if (pLen > sLen) {
return ans;
}
vector<int> sCnt(26, 0);
vector<int> pCnt(26, 0);
for (int i = 0; i < pLen; ++i) {
++pCnt[p[i] - 'a'];
++sCnt[s[i] - 'a'];
}
if (sCnt == pCnt) {
ans.push_back(0);
}
for (int i = 1; i < sLen - pLen + 1; ++i) {
sCnt[s[i-1] - 'a'] -= 1;
sCnt[s[i + pLen - 1] - 'a'] += 1;
if (sCnt == pCnt) {
ans.push_back(i);
}
}
return ans;
}
};
3.无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2：输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3: 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
分析:
1.用滑动窗口对任何一个子串进行无重复判断, 维护窗口内我们搜的是最长的不重复子串
2.为了判断窗口内是无重复的, 我们引入一个 hash表 去记录窗口内每个字符出现的次数
3.如果当前右边指针指向字符发生了重复, 那么就移动左边的窗口
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
if (len <= 1) {
return len;
}
int l = 0;
int r = 0;
int ans = 1;
// 记录无重复窗口里面的字符出现次数
unordered_map<char, int> noRepeatWindowCharCnt;
while (r < len) {
char rc = s[r];
++r;
noRepeatWindowCharCnt[rc] += 1;
// 如果右边指针出现了重复元素, 窗口左侧持续收缩, 直到窗口里面完全无重复 (noRepeatWindowCharCnt[rc] == 1)
while (noRepeatWindowCharCnt[rc] > 1) {
char lc = s[l];
++l;
--noRepeatWindowCharCnt[lc];
}
ans = max(ans, r - l);
}
return ans;
}
};
713.乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：输入：nums = [10,5,2,6], k = 100 输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。示例 2：输入：nums = [1,2,3], k = 0 输出：0
分析:
1.数组都是正整数, 往右乘总乘积就会变大, 左边缩小边界总乘积就会变小, 因此维护滑动窗口
2.当右侧定下来, 左侧也定下来, 满足left .. right < k的情况的时候, 左边到右边中间所有的情况都是满足的
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0 || k <= 1) {
return 0;
}
int ans = 0;
int left = 0;
int right = 0;
int product = 1;
while (right < n) {
product *= nums[right];
while (product >= k) {
product /= nums[left];
++left;
}
ans += right - left + 1;
++right;
}
return ans;
}
};
1004.最大连续1的个数 III
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
}
};
239.滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。
示例 1：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7示例 2：输入：nums = [1], k = 1 输出：[1]
分析:
1.核心思路是如果有一个数据结构能模拟窗口滑动的移动, 那么问题就解决了, 有没有这样的一个数据结构呢? 既要随时取出来最大的元素, 同时满足一个窗口大小是固定的; 为了满足取出来最大的元素, 想到可以持续用大顶堆取顶部元素 pq.top(), 依次取出来最大的那个元素
2.但是怎么模拟窗口大小固定的呢? 可以持续往大顶堆加入元素, 但是保存我们要的结果的时候需要判断一下是否在固定长度的窗口内; 也就是说, 在移动过程中, 队列持续加入元素, 但是最大元素可能不在窗口里面, 需要移除出去最大的元素, 需要注意是要持续移动直到不在窗口内的所有最大元素都移除出去
3.判断不在窗口内方法是队列元素增加一个维度是 index , 如果判断当前窗口添加元素后最大元素应该排除出去, 这时候有 窗口的维护是 [i-k+1, i] 这么 k 个元素, 也就是说窗口元素包含的下界是 [i-k+1], 所以 q.top().second < i - k + 1 都要移除出去
4.举个例子 [9,10,9,-7,-4,-8,2,-6] 窗口大小是 5
移动方法是:
[9,10,9,-7,-4,-8,2,-6] [9,10,9,-7,-4] max = 10
[9,10,9,-7,-4,-8,2,-6] i = 5 队列放入-8 [9,10,9,-7,-4,-8] max=10
[9,10,9,-7,-4,-8,2,-6] i = 6 队列放入2 [9,10,9,-7,-4,-8,2] 最大元素 10 不应该在窗口里面, 删掉10, 变成 [9,9,-7,-4,-8,2], 最大元素9从队列删除, 变成 [9,-7,-4,-8,2] max = 9
[9,10,9,-7,-4,-8,2,-6] i = 7 放入-6 [9,-7,-4,-8,2,-6], 删除最左边的9, max=2
所以最后是 [10,10,9,2]
typedef pair<int, int> pii;
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int len = nums.size();
auto cmp = [] (const pii& a, const pii& b) {
return a.first < b.first;
};
// 建一个 pii 类型大顶堆, 维护 <元素值, index> pair
priority_queue<pii, vector<pii>, decltype(cmp)> pq;
for (int i = 0; i < k; ++i) {
pq.push({nums[i], i});
}
vector<int> ans{pq.top().first};
for (int i = k; i < len; ++i) {
// 开始滑动窗口, 放入元素
pq.push({nums[i], i});
// 当最大元素已经不在窗口内, 持续将最大元素赶出队列
// [i-k+1, i] 是当前的窗口 索引搜索的边界是 idx < i - k + 1
while (pq.top().second < i - k + 1) {
pq.pop();
}
ans.push_back(pq.top().first);
}
return ans;
}
};
1234.替换子串得到平衡字符串
有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。请返回待替换子串的最小可能长度。 如果原字符串自身就是一个平衡字符串，则返回 0。示例 1：输入：s = “QWER” 输出：0 解释：s 已经是平衡的了。
示例 2：输入：s = “QQWE” 输出：1 解释：我们需要把一个 ‘Q’ 替换成 ‘R’，这样得到的 “RQWE” (或 “QRWE”) 是平衡的。
示例 3：输入：s = “QQQW” 输出：2 解释：我们可以把前面的 “QQ” 替换成 “ER”。
示例 4：输入：s = “QQQQ” 输出：3 解释：我们可以替换后 3 个 ‘Q’，使 s = “QWER”。
class Solution {
public:
int balancedString(string s) {
}
};
209.长度最小的子数组
给定一个含有 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
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
}
};
转载请注明来源, from goldandrabbit.github.io
