目录

一、什么是滑动窗口？

二、滑动窗口的适用场景

三、滑动窗口的两种类型

(1) 可变窗口大小

(2) 固定窗口大小

---

一、什么是滑动窗口？

滑动窗口是一种用于处理数组/字符串子区间问题的高效算法技巧，通过维护一个动态的窗口（通常是连续的区间），在遍历数据时调整窗口的左右边界，避免重复计算，从而将时间复杂度优化至 O(n)。

核心思想：

• 窗口由左右指针（left, right）定义，初始时均指向起点。

• right 向右扩展窗口，满足条件时停止。

• left 向右收缩窗口，直到不满足条件。

• 在窗口滑动过程中记录所需结果。

二、滑动窗口的适用场景

• 子串/子数组问题：如“最小覆盖子串”、“最长无重复子串”。

• 连续区间统计：如“和为K的子数组个数”、“平均值最大的子数组”。

• 固定窗口大小问题：如“大小为K的子数组的最大和”。

关键特征：

• 数据为数组或字符串。

• 求解目标与连续子序列相关。

• 暴力解法通常为 O(n²)，滑动窗口可优化至 O(n)。

三、滑动窗口的两种类型

(1) 可变窗口大小

• 窗口大小不固定，根据条件动态扩展或收缩。

例题1. 无重复字符的最长子串

链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

代码：

/**

 * @param {string} s

 * @return {number}

 */

var lengthOfLongestSubstring = function(s) {

    let left = 0 , max = 0 , current = ''

    if(s.length>=1){

        max = 1

        current = s[0]

    }

    for(let i = 1 ; i<s.length ; i++ ){

        let index = current.indexOf(s[i])

        if(index==-1){

            current += s[i]

        }else{

            left = left + index + 1

            current = s.slice(left,i+1)

        }

        max = max>=i-left+1?max:i-left+1

    }

    return max

};

解法二：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length<=1) return s.length;
    let map = new Map(), left = 0, right = 0, max = 1;
    while(right < s.length) {
        let item = map.has(s[right]) && map.get(s[right]);
        if(item === false || item < left) {
            max = max>(right-left+1)?max:right-left+1;
        }else {
            left = item+1;
        }
        map.set(s[right],right);
        right++;
    }
    return max;
};

(2) 固定窗口大小

• 适用于窗口大小固定的问题（如子数组最大平均值）。

 例题1. 找到字符串中所有字母异位词

链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 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" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

代码：

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let len = p.length , current = 0 , arr = [] 
    for(let i = 0 ; i<s.length ; i++ ){
        current = p.indexOf(s[i])!=-1?current+1:0
        if(current==len){
            let t = 0
            for(let j = 0 ; j<len ; j++ ){
                t ^= p[j].charCodeAt(0) ^ s[i-j].charCodeAt(0)
            }
            if(t==0){
                arr.push(i-len+1)
            }
            current--
        }
    }
    return arr
};