滑动窗口（Sliding Window）是一种高效解决数组或字符串中子数组（子串）问题的算法技巧。它通过在数组上维护一个窗口（区间），动态地调整窗口的大小和位置，从而高效地解决问题。本文将详细介绍滑动窗口算法的原理、实现及其应用。
一、算法原理
滑动窗口算法通过在数组上维护一个窗口来解决子数组问题。窗口的大小和位置可以动态调整，以满足不同问题的需求。滑动窗口的基本思想是：
- 初始化窗口的起始位置和结束位置。
- 移动窗口的结束位置，扩展窗口的范围。
- 在窗口范围内进行计算，检查是否满足问题的条件。
- 如果条件不满足，移动窗口的起始位置，缩小窗口的范围。
- 重复步骤2-4，直到遍历完整个数组。
在这里插入图片描述二、算法实现
示例问题1：最长无重复字符子串
给定一个字符串，找出其中不含有重复字符的最长子串的长度。
代码语言：javascript复制/**
* 找出字符串中最长无重复字符子串的长度
* @param {string} s - 输入字符串
* @return {number} - 最长无重复字符子串的长度
*/
function lengthOfLongestSubstring(s) {
const set = new Set();
let left = 0;
let right = 0;
let maxLength = 0;
while (right < s.length) {
if (!set.has(s[right])) {
set.add(s[right]);
right ;
maxLength = Math.max(maxLength, right - left);
} else {
set.delete(s[left]);
left ;
}
}
return maxLength;
}
// 示例
const s = "abcabcbb";
console.log(lengthOfLongestSubstring(s)); // 输出: 3示例问题2：长度最小的子数组
给定一个含有正整数的数组和一个正整数 target，找出该数组中满足其和大于等于 target 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
代码语言：javascript复制/**
* 找出和大于等于 target 的长度最小的子数组的长度
* @param {number} target - 目标和
* @param {number[]} nums - 输入数组
* @return {number} - 长度最小的子数组的长度
*/
function minSubArrayLen(target, nums) {
let left = 0;
let right = 0;
let sum = 0;
let minLength = Infinity;
while (right < nums.length) {
sum = nums[right];
right ;
while (sum >= target) {
minLength = Math.min(minLength, right - left);
sum -= nums[left];
left ;
}
}
return minLength === Infinity ? 0 : minLength;
}
// 示例
const target = 7;
const nums = [2, 3, 1, 2, 4, 3];
console.log(minSubArrayLen(target, nums)); // 输出: 2注释说明：
- 最长无重复字符子串：
set：用于存储窗口内的字符，避免重复。left和right：分别表示窗口的起始位置和结束位置。maxLength：用于记录最长无重复字符子串的长度。while (right < s.length)：遍历字符串。if (!set.has(s[right]))：如果字符不在集合中，加入集合并更新窗口大小和最长长度。else：如果字符在集合中，删除起始位置的字符并移动起始位置。
- 长度最小的子数组：
left和right：分别表示窗口的起始位置和结束位置。sum：用于记录窗口内的子数组和。minLength：用于记录满足条件的最小子数组长度。while (right < nums.length)：遍历数组。while (sum >= target)：如果子数组和大于等于目标值，更新最小长度，并缩小窗口范围。
三、应用场景
- 字符串处理：如查找最长无重复字符子串、包含所有字符的最小子串等。
- 数组处理：如查找和大于等于目标值的最小子数组、固定大小的最大或最小子数组和等。
- 数据流处理：滑动窗口算法可以用于实时处理数据流，计算动态窗口内的数据特征。
四、总结
滑动窗口算法是一种高效解决数组或字符串中子数组（子串）问题的算法技巧，通过动态调整窗口的大小和位置，可以在O(n)时间复杂度内解决许多实际问题。理解和掌握滑动窗口算法，可以有效解决字符串处理、数组处理和数据流处理等问题。
