什么是滑动窗口算法
先用一个简单的题目来说明什么是滑动窗口算法。
最直接的思路就是，对于每个给定的 index，计算出从该 index 开始的一个最小 subarray，其和大于 target:
int minLength = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; ++i) {
int sum = 0;
for (int j = i; j < nums.length; ++j) {
sum += nums[j];
if (sum > target) {
minLength = Math.min(minLength, j - i + 1);
}
break;
}
}
这个算法的问题就在于，相邻的 index 之间，存在着重合的计算。
解决办法就是维护一个滑动窗口，这样就能够解决重复计算的问题了：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int res = Integer.MAX_VALUE, sum = 0, windowStart = 0;
for (int windowEnd = 0; windowEnd < nums.length; ++windowEnd) {
sum += nums[windowEnd];
while (sum >= target) {
res = Math.min(res, windowEnd - windowStart + 1);
sum -= nums[windowStart++];
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
- 每次迭代，将滑动窗口的大小扩大
1，并将nums[windowEnd]加到子数组和sum中。 - 当子数组和
sum > target时，更新结果 - 因为当前子数组和已经比
target大，为求得最优解，我们缩小滑动窗口大小：将滑动窗口的左端的值nums[windowStart]从sum中减去，并将窗口左端点下标加一
总的来说，滑动窗口算法是基于迭代的算法，其使用包括如下步骤：
- 每次迭代扩大滑动窗口的大小：
++windowEnd - 更新窗口左端点
windowStart，使窗口范围的数据是满足题目要求的 - 更新结果
使用到 Map 的题目类型
有些题目需要使用哈希表来记录滑动窗口中数据出现的次数，典型的题目为：567. Permutation in String
这类题目的思路都很接近：
- 用一个 Map（
charCntMap） 来存储目标字符串每个字符的频率 - 用一个
int（cnt）来存储 Map 的大小（charCntMap.size()），即目标字符串（当前题目是s1）有多少个不重复的字符 - 维护一个滑动窗口，每次扩大窗口大小时，如果当前字符出现在 Map 中，将其频率减一
- 当该字符的频率变为 0 时，将
cnt减一；当cnt == 0时，说明目标数组所有字符已经出现在了当前的滑动窗口中，这时更新结果（该题目返回true） - 当滑动窗口非法时（该题目是
窗口大小 > s1.length()），将窗口左端点的index加一（windowStart + 1）；同时：- 如果 Map 存储的该字符出现的频率为 0，则
++cnt，这表明了当前的滑动窗口无法存储目标字符串（s1）所有的字符了 - 将 Map 存储的该字符的频率加一
- 如果 Map 存储的该字符出现的频率为 0，则
Java 实现：
class Solution {
public boolean checkInclusion(String s1, String s2) {
Map<Character, Integer> charCntMap = new HashMap<>();
for (char ch : s1.toCharArray()) {
charCntMap.put(ch, charCntMap.getOrDefault(ch, 0) + 1);
}
int windowStart = 0, cnt = charCntMap.size();
for (int windowEnd = 0; windowEnd < s2.length(); ++windowEnd) {
char ch = s2.charAt(windowEnd);
if (charCntMap.containsKey(ch)) {
charCntMap.put(ch, charCntMap.get(ch) - 1);
if (charCntMap.get(ch) == 0) {
--cnt;
}
}
if (windowEnd - windowStart + 1 > s1.length()) {
ch = s2.charAt(windowStart++);
if (charCntMap.containsKey(ch)) {
charCntMap.put(ch, charCntMap.get(ch) + 1);
if (charCntMap.get(ch) == 1) {
++cnt;
}
}
}
if (cnt == 0) {
return true;
}
}
return false;
}
}
类似的题目有：
使用到 Set 的题目类型
滑动窗口算法有些时候需要配合 HashSet 使用，如 3. Longest Substring Without Repeating Characters:
思路为：
- 维护一个
Set来存储出现在滑动窗口中的元素 - 维护一个滑动窗口，每次迭代的时候检查当前的滑动窗口是否合法，即检查
Set是否有保存窗口右端点对应的元素；窗口非法则说明当前窗口过大，需要缩小窗口大小 - 窗口合法时更新结果值
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0, windowStart = 0;
Set<Character> set = new HashSet<>();
for (int windowEnd = 0; windowEnd < s.length(); ++windowEnd) {
char ch = s.charAt(windowEnd);
if (set.contains(ch)) {
while (set.contains(ch)) {
set.remove(s.charAt(windowStart++));
}
}
set.add(ch);
res = Math.max(res, windowEnd - windowStart + 1);
}
return res;
}
}