滑动窗口算法
在滑动窗口类型的问题中都会有两个指针，一个用于延伸现有窗口的 right 指针，和一个用于收缩窗口的 left 指针。在任意时刻，只有一个指针运动，而另一个保持静止。滑动窗口算法的时间复杂度为 ，因为 right 和 left 两个指针都只移动了 n 次。
该算法的大致逻辑如下：
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
接下来还是看几道典型的 leetcode 题目。
209. 长度最小的子数组 题目描述：
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度
最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。 示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(nlogn) 时间复杂度的解法。
Related Topics 数组 双指针 二分查找
题目分析：
首先想到暴力解法，循环每个子区间，找到满足和大于等于
s 的子区间，更新最小长度。class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if nums is None or len(nums) == 0:
return 0
n = len(nums)
res = n + 1
for i in range(n):
numSums = 0
for j in range(i, n):
numSums += nums[j]
if numSums >= s:
res = min(res, j-i+1)
break
return 0 if res == n+1 else res
此时时间复杂度 ，题目提示复杂度应为 ，那需要在常数次遍历中找到答案。在暴力解法中，我们先固定
i，然后增加 j，一次结束后，我们将 i 加 1，然后再循环 j，重复的计算主要在这里。那是不是可以保持 j 在上一次循环结束的地方不动呢？我们知道上一次循环结束后 i 和 j 之间的子数组的和大于等于 s，如果此时 j 不动，然后 i 加 1，那我们求得的和就需要减掉 nums[i]，如果此时的子数组的和满足条件，那最小长度比开始更小了，那我们需要更新最小长度；如果此时子数组的和不满足条件，那我们继续增加 j，来扩大子数组的长度。这也就是我们的滑动窗口思路。class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if nums is None or len(nums) == 0:
return 0
left, right, numSum = 0, 0, 0
res = len(nums) + 1
while right < len(nums):
# 扩大窗口
numSum += nums[right]
while numSum >= s:
res = min(res, right-left+1)
# 缩小窗口
numSum -= nums[left]
left += 1
right += 1
return 0 if res == len(nums) + 1 else res
76. 最小覆盖子串 题目描述：
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。 示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。 Related Topics 哈希表 双指针 字符串 Sliding Window
联系滑动窗口算法，首先我们增大窗口，当条件满足时，缩小窗口。考虑到
t中可能有重复字符，所以我们的判断条件还需要考虑每个字符的数量一致。class Solution:
def minWindow(self, s: str, t: str) -> str:
if s is None or t is None:
return ''
left, right, valid = 0, 0, 0
start, length = 0, len(s)+1
need, windown = {}, {}
for i in t:
need.setdefault(i, 0)
need[i] += 1
while right < len(s):
# 增大窗口
if s[right] in need:
windown.setdefault(s[right], 0)
windown[s[right]] += 1
if need[s[right]] == windown[s[right]]:
valid += 1
right += 1
# 条件满足
while valid == len(need):
if right - left < length:
length = min(length, right-left)
start = left
# 缩减窗口
if s[left] in need:
if windown[s[left]] == need[s[left]]:
valid -= 1
windown[s[left]] -= 1
left += 1
return '' if length == len(s)+1 else s[start: start+length+1]
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" 的字母异位词。Related Topics 哈希表
题目分析：
这道题需要关注的窗口为固定长度。我们先不考虑这个点，看看普通的滑动窗口解法：
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
need, windown = {}, {}
res = []
left, right, valid = 0, 0, 0
for a in p:
need.setdefault(a, 0)
need[a] += 1
while right < len(s):
b = s[right]
right += 1
if b in need:
windown.setdefault(b, 0)
windown[b] += 1
if need[b] == windown[b]:
valid += 1
while valid == len(need):
if right - left == len(p):
res.append(left)
c = s[left]
if c in windown:
if windown[c] == need[c]:
valid -= 1
windown[c] -= 1
left +=1return res
这个解法中，我们是等到子字符串满足条件了再来缩减窗口。由于题目所述为固定的窗口大小，那我们缩减窗口的条件可以改成如下形式：
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
need, windown = {}, {}
res = []
left, right, valid = 0, 0, 0
for a in p:
need.setdefault(a, 0)
need[a] += 1
while right < len(s):
b = s[right]
right += 1
if b in need:
windown.setdefault(b, 0)
windown[b] += 1
if need[b] == windown[b]:
valid += 1
# 这里用 if 判断亦可
while right - left >= len(p):
if valid == len(need):
res.append(left)
c = s[left]
left +=1
if c in need:
# 这个判断条件很重要，只有当相等的时候才需要将 valid 减 1
if windown[c] == need[c]:
valid -= 1
windown[c] -= 1
return res
567. 字符串的排列 题目描述：
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间 Related Topics 双指针 Sliding Window
【滑动窗口算法】和上一题类似，我们还是套用滑动窗口模板：
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
need, windown = {}, {}
for a in s1:
need.setdefault(a, 0)
need[a] += 1
left, right, valid = 0, 0, 0
while right < len(s2):
b = s2[right]
right += 1
if b in need:
windown.setdefault(b, 0)
windown[b] += 1
if windown[b] == need[b]:
valid += 1
# 缩小窗口
if right - left >= len(s1):
# 判断是否满足题目要求
if valid == len(need):
return True
c = s2[left]
left += 1
if c in need:
if windown[c] == need[c]:
valid -= 1
windown[c] -= 1
return False
3. 无重复字符的最长子串 题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。Related Topics 哈希表 双指针 字符串 Sliding Window
题目分析：
题目的条件是无重复字符，那我们滑动窗口的条件便是：没有重复字符时，我们增大窗口，出现重复字符时我们缩小滑动窗口。需要注意的是我们更新结果再增加窗口的步骤中。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 无重复字符，我们增加窗口；有重复字符时，我们缩小窗口
windown = set()
left, right, valid = 0, 0, 0
res = 0
while right < len(s):
a = s[right]
right += 1
# 有重复字符，需要缩减窗口
while a in windown:
b = s[left]
left += 1
windown.remove(b)
else:
windown.add(a)
res = max(right-left, res)
return res
参考
- https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法