滑动窗口算法
本
简介
滑动窗口是一种双指针算法。它指的是这样一类问题的求解方法,在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字,它们的解法其实是很自然的。
使用滑动窗口解决的问题通常是暴力解法的优化,掌握这一类问题最好的办法就是练习,然后思考清楚为什么可以使用滑动窗口。
力扣相关算法题:https://leetcode.cn/tag/sliding-window/problemset/
应用场景
关键词
- 满足 xxx 条件(计算结果,出现次数,同时包含)
- 最长/最短
- 子串/子数组/子序列(通常连续)
例如:长度最小的子数组
使用思路
示例图解

示例演示

寻找最长
- 核心: 左右双指针(L,R)在起始点,R 向右逐位滑动循环
- 每次滑动过程中:
- 如果:窗内元素满足条件,R 向右扩大窗口,并更新最优结果
- 如果:窗内元素不满足条件,L 向右缩小窗口
- R 到达结尾
寻找最短
- 核心: 左右双指针(L,R)在起始点,R 向右逐位滑动循环
- 每次滑动过程中:
- 如果:窗内元素满足条件,L 向右缩小窗口,并更新最优结果
- 如果:窗内元素不满足条件,R 向右扩大窗口
- R 到达结尾
解题模板
最长模板
c++
初始化变量 left, right, result, bestResult
while (right 没有到达结尾) {
窗口扩大,加入right对应元素,更新当前 result
while (result 不满足要求) {
窗口缩小,移除 left 对应元素,left 右移
}
更新最优结果 bestResult
right++;
}
return bestResult
最短模板
c++
初始化变量 left, right, result, bestResult
while (right 没有到达结尾) {
窗口扩大,加入right对应元素,更新当前 result
while (result 满足要求) {
更新最优结果 bestResult
窗口缩小,移除 left 对应元素,left 右移
}
right++;
}
return bestResult
例题
长度最小的子数组
题目:209.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
解法
java
/**
* 209. 长度最小的子数组
* https://leetcode.cn/problems/minimum-size-subarray-sum/
*
* @author Salmon
* @since 2023-12-07
*/
public class M_209 {
public static void main(String[] args) {
System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
System.out.println(minSubArrayLen(4, new int[]{1, 4, 4}));
System.out.println(minSubArrayLen(11, new int[]{1, 1, 1, 1, 1, 1, 1, 1}));
}
public static int minSubArrayLen(int target, int[] nums) {
int right = 0, left = 0, curSum = 0, minLength = 0;
// 判断 right 是否到达结尾
while (right < nums.length) {
curSum += nums[right];
// 判断当前是否满足条件,满足条件则进入循环
// 判断每次缩小后的窗口是否满足满足条件
while (curSum >= target) {
// 更新当前窗口中的数组长度,minLength=0:第一次满足条件时需更新下最短长度
if (minLength == 0 || right - left + 1 < minLength) {
minLength = right - left + 1;
}
// 缩小窗口
curSum -= nums[left];
// 左指针右移
left++;
}
right++;
}
return minLength;
}
}
重复的DNA序列
DNA序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.。
- 例如,
"ACGAATTCCG"是一个 DNA序列 。
在研究 DNA 时,识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC","CCCCCAAAAA"]
示例 2:
输入:s = "AAAAAAAAAAAAA"
输出:["AAAAAAAAAA"]
提示:
0 <= s.length <= 105s[i]=='A'、'C'、'G'or'T'
解法1:直接使用 hash 表统计,简单。
java
import java.util.*;
/**
* 187. 重复的DNA序列
* https://leetcode.cn/problems/repeated-dna-sequences/
*
* @author Salmon
* @since 2023-12-07
*/
public class M_187 {
static final int L = 10;
public static void main(String[] args) {
List<String> sequences = findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
System.out.print("[");
for (int i = 0; i < sequences.size(); i++) {
System.out.print(sequences.get(i));
if (i < sequences.size() - 1) {
System.out.print(",");
}
}
System.out.println("]");
}
public static List<String> findRepeatedDnaSequences(String s) {
List<String> res = new ArrayList<>();
int n = s.length();
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i <= n - L; ++i) {
String sub = s.substring(i, i + L);
map.put(sub, map.getOrDefault(sub, 0) + 1);
if (map.get(sub) == 2) {
res.add(sub);
}
}
return res;
}
}
解法2:哈希表 + 滑动窗口 + 位运算
java
import java.util.*;
/**
* 187. 重复的DNA序列
* https://leetcode.cn/problems/repeated-dna-sequences/
*
* @author Salmon
* @since 2023-12-07
*/
public class M_187 {
public static void main(String[] args) {
List<String> sequences = findRepeatedDnaSequences1("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
// List<String> sequences = findRepeatedDnaSequences1("AAAAAAAAAAA");
System.out.print("[");
for (int i = 0; i < sequences.size(); i++) {
System.out.print(sequences.get(i));
if (i < sequences.size() - 1) {
System.out.print(",");
}
}
System.out.println("]");
}
static final int L = 10;
static Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
put('A', 0);
put('C', 1);
put('G', 2);
put('T', 3);
}};
public static List<String> findRepeatedDnaSequences1(String s) {
List<String> res = new ArrayList<>();
int n = s.length();
if (n <= L) {
return res;
}
int x = 0;
// 初始化:先累计前 9 个的序列数值
for (int i = 0; i < L - 1; i++) {
// 求 x左移2位相当于x乘2的平方 然后与当前字符的映射值作或运算
x = (x << 2) | bin.get(s.charAt(i));
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i <= n - L; i++) {
// 将当前的 x 与第10个数字的
x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);
map.put(x, map.getOrDefault(x, 0) + 1);
// 如果重复出现
if (map.get(x) == 2) {
res.add(s.substring(i, i + L));
}
}
return res;
}
}