[算法]滑动窗口

适用场景

• 题目要求 连续子串 或 连续子数组
• 需要求 最长、最短
• 窗口满足某个限制条件，比如不重复、和至少为某值、包含某些字符

核心思路

• 用两个指针维护一个区间 [left, right]
• right 负责扩张窗口
• 当窗口不满足条件时，不断移动 left 缩小窗口
• 每次窗口合法时更新答案

Rust 模板

fn window_template(nums: Vec<i32>) -> i32 {
    let mut left = 0usize;
    let mut ans = 0i32;

    for right in 0..nums.len() {
        // 1. 扩张窗口

        while false {
            // 2. 缩小窗口直到重新合法
            left += 1;
        }

        // 3. 更新答案
        ans = ans.max((right - left + 1) as i32);
    }

    ans
}

无重复字符的最长子串

fn length_of_longest_substring(s: String) -> i32 {
    let mut left = 0usize;
    let mut ans = 0usize;
    let mut count = [0; 128];

    for (right, b) in s.bytes().enumerate() {
        let idx = b as usize;
        count[idx] += 1;

        while count[idx] > 1 {
            count[s.as_bytes()[left] as usize] -= 1;
            left += 1;
        }

        ans = ans.max(right - left + 1);
    }

    ans as i32
}

代表题

• 3. 无重复字符的最长子串
  题意：给定一个字符串，求其中不含重复字符的最长连续子串长度。

use std::collections::HashSet;

fn length_of_longest_substring(s: String) -> i32 {
    let s = s.as_bytes();          // 转为字节切片，便于索引
    let mut left = 0usize;
    let mut ans = 0i32;
    let mut window = HashSet::new(); // 用于记录窗口内出现的字符

    for right in 0..s.len() {
        // 1. 扩张窗口：将 s[right] 加入窗口
        // 2. 如果 s[right] 已存在，则收缩窗口直到重复字符被移除
        while window.contains(&s[right]) {
            window.remove(&s[left]); // 移除左指针指向的字符
            left += 1;               // 左指针右移
        }
        // 此时窗口内没有重复字符，将 s[right] 正式加入
        window.insert(s[right]);

        // 3. 更新答案（当前窗口长度为 right - left + 1）
        ans = ans.max((right - left + 1) as i32);
    }
    ans
}

• 438. 找到字符串中所有字母异位词
  题意：给定字符串 s 和 p，找出 s 中所有与 p 互为字母异位词的子串起始下标。

pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
    let s = s.as_bytes();
    let p = p.as_bytes();
    let p_len = p.len();
    
    // 如果 s 比 p 短，不可能有异位词
    if s.len() < p_len {
        return vec![];
    }

    let mut left = 0usize;
    let mut ans = Vec::new();          // 改为存储索引的 Vec

    // 因为题目限定为小写字母，用长度为 26 的数组作为计数器
    let mut target = [0i32; 26];
    let mut window = [0i32; 26];

    // 统计 p 中每个字符的出现次数
    for &b in p {
        target[(b - b'a') as usize] += 1;
    }

    for right in 0..s.len() {
        // 1. 扩张窗口：将 s[right] 加入窗口
        window[(s[right] - b'a') as usize] += 1;

        // 2. 缩小窗口：直到窗口长度 == p_len（固定窗口特性）
        while (right - left + 1) > p_len {
            window[(s[left] - b'a') as usize] -= 1;
            left += 1;
        }

        // 3. 更新答案：当窗口长度刚好等于 p_len，且字符频率完全匹配
        if (right - left + 1) == p_len && window == target {
            ans.push(left as i32);
        }
    }
    ans
}

• 76. 最小覆盖子串
  题意：给定字符串 s 和 t，在 s 中找到一个最短的连续子串，使它包含 t 中所有字符及其出现次数。

use std::collections::VecDeque;

pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut left = 0usize;
    let mut ans = Vec::new();
    let mut deque: VecDeque<usize> = VecDeque::new(); // 存储索引，队首为当前窗口最大值索引

    for right in 0..nums.len() {
        // 1. 扩张窗口：将新元素下标加入单调队列（维护递减）
        while !deque.is_empty() && nums[*deque.back().unwrap()] <= nums[right] {
            deque.pop_back();
        }
        deque.push_back(right);

        // 2. 收缩窗口：如果窗口大小超过 k，左移 left（同时移除队列中不在窗口内的索引）
        while (right - left + 1) > k {
            // 如果队首就是 left，则弹出
            if let Some(&front) = deque.front() {
                if front == left {
                    deque.pop_front();
                }
            }
            left += 1;
        }

        // 3. 更新答案：当窗口长度 == k 时，记录队首元素（当前窗口最大值）
        if (right - left + 1) == k {
            ans.push(nums[*deque.front().unwrap()]);
        }
    }
    ans
}

• 209. 长度最小的子数组
  题意：给定一个正整数数组和一个目标值 target，找出和大于等于 target 的最短连续子数组长度；如果不存在则返回 0。

use std::collections::HashMap;

pub fn min_window(s: String, t: String) -> String {
    let s = s.as_bytes();
    let t = t.as_bytes();
    let mut need = HashMap::new();
    for &b in t {
        *need.entry(b).or_insert(0) += 1;
    }
    let mut window = HashMap::new();
    let mut left = 0usize;
    let mut valid = 0;          // 已满足的字符种类数
    let mut min_len = usize::MAX;
    let mut start = 0;

    for right in 0..s.len() {
        // 1. 扩张窗口：将 s[right] 加入窗口
        let c = s[right];
        *window.entry(c).or_insert(0) += 1;
        if need.contains_key(&c) && window[&c] == need[&c] {
            valid += 1;
        }

        // 2. 收缩窗口：当窗口完全覆盖 t 时，尝试左移缩小
        while valid == need.len() {
            // 3. 更新答案（在收缩过程中记录最小窗口）
            let cur_len = right - left + 1;
            if cur_len < min_len {
                min_len = cur_len;
                start = left;
            }

            // 将要移出窗口的字符是 s[left]
            let d = s[left];
            if need.contains_key(&d) && window[&d] == need[&d] {
                valid -= 1;
            }
            *window.get_mut(&d).unwrap() -= 1;
            left += 1;
        }
        // 注意：收缩条件为 `while valid == need.len()`，当收缩后不再满足覆盖时，循环结束，继续扩张 right
    }

    if min_len == usize::MAX {
        "".to_string()
    } else {
        String::from_utf8(s[start..start + min_len].to_vec()).unwrap()
    }
}