/* 滑动窗口算法框架 */
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:
def minWindow(self, s: str, t: str) -> str:
target = collections.defaultdict(int)
window = collections.defaultdict(int)
for c in t:
target[c] += 1
min_size = len(s) + 1
min_str = ''
l, r, count, num_char = 0, 0, 0, len(target)
while r < len(s):
c = s[r]
r += 1
if c in target:
window[c] += 1
if window[c] == target[c]:
count += 1
if count == num_char:
while l < r and count == num_char:
c = s[l]
l += 1
if c in target:
window[c] -= 1
if window[c] == target[c] - 1:
count -= 1
if min_size > r - l + 1:
min_size = r - l + 1
min_str = s[l - 1:r]
return min_str
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 **s1 **的排列。
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
target = collections.defaultdict(int)
for c in s1:
target[c] += 1
r, num_char = 0, len(target)
while r < len(s2):
if s2[r] in target:
l, count = r, 0
window = collections.defaultdict(int)
while r < len(s2):
c = s2[r]
if c not in target:
break
window[c] += 1
if window[c] == target[c]:
count += 1
if count == num_char:
return True
while window[c] > target[c]:
window[s2[l]] -= 1
if window[s2[l]] == target[s2[l]] - 1:
count -= 1
l += 1
r += 1
else:
r += 1
return False
给定一个字符串 **s **和一个非空字符串 p，找到 **s **中所有是 **p **的字母异位词的子串，返回这些子串的起始索引。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
target = collections.defaultdict(int)
for c in p:
target[c] += 1
r, num_char = 0, len(target)
results = []
while r < len(s):
if s[r] in target:
l, count = r, 0
window = collections.defaultdict(int)
while r < len(s):
c = s[r]
if c not in target:
break
window[c] += 1
if window[c] == target[c]:
count += 1
if count == num_char:
results.append(l)
window[s[l]] -= 1
count -= 1
l += 1
while window[c] > target[c]:
window[s[l]] -= 1
if window[s[l]] == target[s[l]] - 1:
count -= 1
l += 1
r += 1
else:
r += 1
return results
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last_idx = {}
l, max_length = 0, 0
for r, c in enumerate(s):
if c in last_idx and last_idx[c] >= l:
max_length = max(max_length, r - l)
l = last_idx[c] + 1
last_idx[c] = r
return max(max_length, len(s) - l) # note that the last substring is not judged in the loop
- 和双指针题目类似，更像双指针的升级版，滑动窗口核心点是维护一个窗口集，根据窗口集来进行处理
- 核心步骤