滑动窗口算法模板
class Solution {vector<int>slidingWindowTemplate(string s, string t){vector<int>result;if(s.size() < t.size())return result;//创建hashmap用于保存目标字符串map<char, int>slide;for(auto &ch : t)slide[ch]++;//必须是hashmap的大小，不能是目标字符串的大小，//因为目标字符串中可能会有重复的字符int counter = slide.size();//两个指针，begin指向窗口的左边界，end指向窗口的右边界int begin = 0, end = 0;int len = MAX_INT;while(end < s.size()){char c = s[end];if(slide.find(c) != slide.end()){slide[c]--;//根据需求的不同来修改计数器if(slide[c] == 0)counter--;}end++;//counter为0表示所有的字符都已经存在于窗口当中，//窗口的某些字符可能多于目标字符串的字符，//但是这些字符绝无可能小于目标字符串的字符//否则counter是无法清零的while(counter == 0){char tempc = s[begin];if(slide.find(tempc) != slide.end()){slide[tempc]--;//一旦counter大于0，意味着窗口中的目标字符数小于了目标字符//此时继续移动窗口有边界，从而执行消除操作if(slide[tempc] > 0)counter++;}begin++;}}return result;}};
例题
例题一：最小覆盖字串
76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入: S = “ADOBECODEBANC”, T = “ABC” 输出: “BANC” 说明：
如果 S 中不存这样的子串，则返回空字符串 “”。 如果 S 中存在这样的子串，我们保证它是唯一的答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
string minWindow(string s, string t) {
int size_s = s.size();
int size_t = t.size();
if(s == t)
return t;
string ret;
if(size_s < size_t || size_t == 0 || size_s == 0)
return ret;
map<char, int>window;
for(auto &ch : t)
window[ch]++;
int counter = window.size();
int begin = 0, end = 0, startindex = 0, endindex = 0;
int window_size = INT_MAX;
while(end < size_s)
{
char c = s[end];
if(window.find(c) != window.end())
{
window[c]--;
if(window[c] == 0)
counter--;
}
end++;
while(counter == 0)
{
char tmp = s[begin];
if(end - begin < window_size)
{
window_size = end - begin;
startindex = begin;
endindex = end;
}
if(window.find(tmp) != window.end())
{
window[tmp]++;
if(window[tmp] > 0)
counter++;
}
begin++;
}
}
return s.substr(startindex, endindex - startindex);
}
};
例题二：找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 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” 的字母异位词。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int size_s = s.size();
int size_p = p.size();
vector<int>ret;
if(size_s < size_p || size_s == 0 || size_p == 0)
return ret;
if(s == p)
{
ret.push_back(0);
return ret;
}
map<char, int>anagrams;
for(auto &ch : p)
anagrams[ch]++;
int begin = 0, end = 0;
int counter = anagrams.size();
while(end < size_s)
{
char c = s[end];
if(anagrams.find(c) != anagrams.end())
{
anagrams[c]--;
if(anagrams[c] == 0)
counter--;
}
end++;
while(counter == 0)
{
char tmpc = s[begin];
//如果窗口长度刚好等于目标字符串的长度，并且counter还是0
//那么就一定满足目标字符串的要求了
if(end - begin == size_p)
ret.push_back(begin);
if(anagrams.find(tmpc) != anagrams.end())
{
if(anagrams[tmpc] == 0)
counter++;
anagrams[tmpc]++;
}
begin++;
}
}
return ret;
}
};
例题三：无重复字符的最长子串
3 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int size = s.size();
if(size == 0)
return 0;
if(size == 1)
return 1;
int begin = 0, end = 0;
map<char, int>sub;
//if not equal to 0, it means still exist duplicate
int counter = 0;
int ret = INT_MIN;
while(end < size)
{
char c = s[end];
if(sub.find(c) == sub.end())
{
if(sub.size() > ret)
ret = sub.size();
sub[c]++;
//这里当end和begin相同时，至少是由1个字符的
//所以需要加1
ret = max(ret, end - begin + 1);
}
else if(sub.find(c) != sub.end())
{
if(sub[c] == 1)
counter++;
sub[c]++;
}
end++;
while(counter != 0)
{
char tempc = s[begin];
if(sub.find(tempc) != sub.end())
{
sub[tempc]--;
if(sub[tempc] == 1)
counter--;
if(sub[tempc] == 0)
sub.erase(tempc);
}
begin++;
}
//这里不需要加1，都是不一样的字符
ret = max(ret, end - begin);
}
return ret;
}
};
简洁的答案
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
复杂度分析
时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)[0,128) 内的字符，即128∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 |∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。
下面的是我采用vector作为滑动窗口的方法，其劣势在于find会影响到整个程序的执行时间
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0)
return 0;
vector<char>dict;
int leftptr = 0;
int rightptr = 0;
int ret = 0;
for(; rightptr < s.size(); rightptr++)
{
auto it = find(dict.begin(), dict.end(), s[rightptr]);
if(it != dict.end())
{
leftptr = leftptr + distance(it, dict.end());
dict.erase(it, dict.end());
}
dict.insert(dict.begin(), s[rightptr]);
ret = ret > rightptr - leftptr + 1 ? ret : rightptr - leftptr + 1;
}
return ret;
}
};
例题四：字符串的排列
567. 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int size_s1 = s1.size();
int size_s2 = s2.size();
if(size_s1 > size_s2)
return false;
if(s1 == s2)
return true;
int begin = 0, end = 0;
map<char, int>clusion;
for(auto &ch : s1)
clusion[ch]++;
int counter = clusion.size();
while(end < size_s2)
{
char c = s2[end];
if(clusion.find(c) != clusion.end())
{
clusion[c]--;
if(clusion[c] == 0)
counter--;
}
end++;
while(counter == 0)
{
char tmpc = s2[begin];
if(end - begin == size_s1)
return true;
if(clusion.find(tmpc) != clusion.end())
{
clusion[tmpc]++;
if(clusion[tmpc] == 1)
counter++;
}
begin++;
}
}
return false;
}
};
例题五：最大连续1的个数III
1004. 最大连续1的个数 III
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。 返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [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：
输入：A = [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。
提示：
1 <= A.length <= 20000 0 <= K <= A.length A[i] 为 0 或 1
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int i = 0, j;
for(j = 0; j < nums.size(); j++)
{
if(nums[j] == 0) k--;
if(k < 0 && nums[i++] == 0) k++;
}
return j - i;
}
};
若有收获，就点个赞吧
0 人点赞
