滑动窗口思想
模板
/* 滑动窗口算法框架 */
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++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}需要变化的地方
1、右指针右移之后窗口数据更新
2、判断窗口是否要收缩
3、左指针右移之后窗口数据更新
4、根据题意计算结果
示例
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串
class Solution {
String minWindow(String s, String t) {
// 初始化计数数组freq，用于记录t中每个字符出现的次数
var freq = List<int>.filled(128, 0);
for (var c in t.codeUnits) {
freq[c]++;
}
// 初始化左右指针、最小长度、起始位置和字符匹配计数器
var left = 0, right = 0, minLen = s.length + 1, start = 0, count = t.length;
// 移动右指针，扩大窗口
while (right < s.length) {
// 如果右指针指向的字符出现在t中，则计数器减1
if (freq[s.codeUnitAt(right++)]-- > 0) {
count--;
}
// 如果当前窗口包含了t中的所有字符，则移动左指针，缩小窗口
while (count == 0) {
// 更新最小覆盖子串的长度和起始位置
if (right - left < minLen) {
minLen = right - left;
start = left;
}
// 如果左指针指向的字符出现在t中，则计数器加1
if (freq[s.codeUnitAt(left++)]++ == 0) {
count++;
}
}
}
// 如果最小覆盖子串的长度为s.length+1，则不存在符合要求的子串，返回空字符串
// 否则，返回最小覆盖子串
return minLen == s.length + 1 ? '' : s.substring(start, start + minLen);
}
}给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 **s1 **的排列。
class Solution {
bool checkInclusion(String s1, String s2) {
var freq = List<int>.filled(128, 0);
// 统计 s1 中每个字符出现的次数
for (var c in s1.codeUnits) {
freq[c]++;
}
var left = 0, right = 0, count = s1.length;
while (right < s2.length) {
// 如果当前字符在 s1 中出现过，则减少其在 freq 数组中的出现次数
if (freq[s2.codeUnitAt(right++)]-- > 0) {
count--;
}
// 如果 s1 中所有字符都出现在了当前窗口中，则返回 true
if (count == 0) {
return true;
}
// 如果当前窗口大小已经等于 s1 的长度了，则需要缩小窗口
if (right - left == s1.length) {
// 如果左边界字符在 s1 中出现过，则需要增加其在 freq 数组中的出现次数
if (freq[s2.codeUnitAt(left++)]++ >= 0) {
count++;
}
}
}
// 如果遍历整个 s2 都没找到符合条件的子串，则返回 false
return false;
}
}
给定一个字符串 **s **和一个非空字符串 p，找到 **s **中所有是 **p **的字母异位词的子串，返回这些子串的起始索引。
class Solution {
List<int> findAnagrams(String s, String p) {
var result = <int>[];
// 记录p中每个字符出现的次数
var target = List<int>.filled(26, 0);
for (var i = 0; i < p.length; i++) {
target[p.codeUnitAt(i) - 97]++;
}
var left = 0, right = 0, count = p.length;
// 移动右指针，扩大窗口
while (right < s.length) {
// 如果当前字符在p中出现过，则count减1
if (target[s.codeUnitAt(right++) - 97]-- > 0) {
count--;
}
// 如果count变为0，说明窗口中包含了p中所有字符的排列，将左指针加入结果数组
if (count == 0) {
result.add(left);
}
// 当窗口大小等于p的长度时，移动左指针，缩小窗口
if (right - left == p.length) {
// 如果当前左指针指向的字符在p中出现过，则count加1
if (target[s.codeUnitAt(left++) - 97]++ >= 0) {
count++;
}
}
}
return result;
}
}
longest-substring-without-repeating-characters
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
class Solution {
int lengthOfLongestSubstring(String s) {
int n = s.length;
Set<String> set = Set(); // 用 Set 记录当前窗口中出现的字符
int ans = 0, i = 0, j = 0; // ans 记录最长子串长度，i 和 j 记录窗口左右边界
while (i < n && j < n) { // 右指针 j 向右移动，直到字符串末尾
if (!set.contains(s[j])) { // 如果当前字符不在窗口中，加入窗口
set.add(s[j++]);
ans = ans > j - i ? ans : j - i; // 更新最长子串长度
} else { // 如果当前字符已经在窗口中，左指针 i 向右移动，缩小窗口
set.remove(s[i++]);
}
}
return ans;
}
}总结
和双指针题目类似，更像双指针的升级版，滑动窗口核心点是维护一个窗口集，根据窗口集来进行处理
核心步骤
right 右移
收缩
left 右移
求结果
练习
Last updated