滑动窗口
模板
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}需要变化的地方
1、右指针右移之后窗口数据更新
2、判断窗口是否要收缩
3、左指针右移之后窗口数据更新
4、根据题意计算结果
示例
最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串
public String minWindow(String s, String t) {
// 技巧：用数组代替Map
// 保存滑动窗口字符集
int[] winMap = new int[256];
// 保存需要出现的字符集
int[] tMap = new int[256];
for (char c : t.toCharArray()) {
tMap[c]++;
}
// 计算共出现了多少不同的字符
int charNum = 0;
for (int n : tMap) {
if (n > 0) {
charNum++;
}
}
// 滑动窗口左右边界
int left = 0;
int right = 0;
// 匹配数
int match = 0;
// 窗口调整前暂存原窗口边界
int start = 0;
int end = 0;
// 窗口长度的最小值
int minValue = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
// 在需要的字符集里面，添加到窗口字符集里面
if (tMap[c] != 0) {
winMap[c]++;
// 如果当前字符的数量匹配需要的字符的数量，则match值+1
if (tMap[c] == winMap[c]) {
match++;
}
}
right++;
// 当所有字符数量都匹配之后，开始缩紧窗口
while (match == charNum) {
// 获取结果
if (right - left < minValue) {
minValue = right - left;
start = left;
end = right;
}
char leftChar = s.charAt(left);
// 左指针指向不在需要字符集则直接跳过
if (tMap[leftChar] != 0) {
// 左指针指向字符数量和需要的字符相等时，右移之后match值就不匹配则减一
if (winMap[leftChar] == tMap[leftChar]) {
match--;
}
winMap[leftChar]--;
}
left++;
}
}
if (minValue == Integer.MAX_VALUE) {
return "";
}
return s.substring(start, end);
}字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
public boolean checkInclusion(String s1, String s2) {
// 保存滑动窗口字符集
int[] winMap = new int[256];
// 保存需要出现的字符集
int[] tMap = new int[256];
for (char c : s1.toCharArray()) {
tMap[c]++;
}
// 计算共出现了多少不同的字符
int charNum = 0;
for (int n : tMap) {
if (n > 0) {
charNum++;
}
}
// 左右边界
int left = 0;
int right = 0;
// 已经匹配的字母数
int match = 0;
while (right < s2.length()) {
char c = s2.charAt(right);
right++;
if (tMap[c] != 0) {
winMap[c]++;
if (winMap[c] == tMap[c]) {
match++;
}
}
// 窗口收缩
while (match == charNum) {
c = s2.charAt(left);
if (tMap[c] != 0) {
if (winMap[c] == tMap[c]) {
match--;
}
winMap[c]--;
}
left++;
// 子串是一个排列，即子串长度等于s1
if (right - left + 1 == s1.length()) {
return true;
}
}
}
return false;
}找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
public List<Integer> findAnagrams(String s, String p) {
int[] pMap = new int[256];
int[] winMap = new int[256];
int charNum = 0;
for (char c : p.toCharArray()) {
if (pMap[c] == 0) charNum++;
pMap[c]++;
}
int left = 0;
int right = 0;
int match = 0;
List<Integer> result = new ArrayList<>();
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (pMap[c] != 0) {
winMap[c]++;
if (pMap[c] == winMap[c]) {
match++;
}
}
// 缩紧窗口
while (match == charNum) {
c = s.charAt(left);
if (pMap[c] != 0) {
if (pMap[c] == winMap[c]) {
match--;
}
winMap[c]--;
}
// 当窗口长度和字符串长度匹配时，满足条件
if (right - left == p.length()) {
result.add(left);
}
left++;
}
}
return result;
}无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
public int lengthOfLongestSubstring(String s) {
if (s.length() < 2) {
return s.length();
}
int[] winMap = new int[256];
int left = 0;
int right = 0;
int maxLen = 0;
// 1、右指针右移
while (right < s.length()) {
char c = s.charAt(right);
right++;
winMap[c]++;
// 2、根据题意收缩窗口
while (winMap[c] > 1) {
// 3、左指针右移更新窗口
char d = s.charAt(left);
left++;
winMap[d]--;
}
// 4、根据题意计算结果
maxLen = Math.max(right - left, maxLen);
}
return maxLen;
}总结
和双指针题目类似，更像双指针的升级版，滑动窗口核心点是维护一个窗口集，根据窗口集来进行处理
核心步骤
right 右移
收缩
left 右移
求结果
最后更新于