[算法]滑动窗口

适用场景

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

核心思路

• 用两个指针维护一个区间 [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() {
        while window.contains(&s[right]) {
            window.remove(&s[left]);
            left += 1;
        }

        window.insert(s[right]);
        ans = ans.max((right - left + 1) as i32);
    }

    ans
}

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

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 = 0usize;
    let mut start = 0usize;
    let mut min_len = usize::MAX;

    for right in 0..s.len() {
        let c = s[right];
        *window.entry(c).or_insert(0) += 1;

        if need.contains_key(&c) && window[&c] == need[&c] {
            valid += 1;
        }

        while valid == need.len() {
            let cur_len = right - left + 1;
            if cur_len < min_len {
                min_len = cur_len;
                start = left;
            }

            let d = s[left];
            if need.contains_key(&d) && window[&d] == need[&d] {
                valid -= 1;
            }
            *window.get_mut(&d).unwrap() -= 1;
            left += 1;
        }
    }

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

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

pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
    let mut left = 0usize;
    let mut sum = 0i32;
    let mut ans = usize::MAX;

    for right in 0..nums.len() {
        sum += nums[right];

        while sum >= target {
            ans = ans.min(right - left + 1);
            sum -= nums[left];
            left += 1;
        }
    }

    if ans == usize::MAX {
        0
    } else {
        ans as i32
    }
}

• 239. 滑动窗口最大值
  题意：给定一个数组和窗口大小 k，窗口从左到右滑动，返回每个窗口中的最大值。

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() {
        while !deque.is_empty() && nums[*deque.back().unwrap()] <= nums[right] {
            deque.pop_back();
        }
        deque.push_back(right);

        while (right - left + 1) > k {
            if let Some(&front) = deque.front() {
                if front == left {
                    deque.pop_front();
                }
            }
            left += 1;
        }

        if (right - left + 1) == k {
            ans.push(nums[*deque.front().unwrap()]);
        }
    }

    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();

    if s.len() < p_len {
        return vec![];
    }

    let mut left = 0usize;
    let mut ans = Vec::new();
    let mut target = [0i32; 26];
    let mut window = [0i32; 26];

    for &b in p {
        target[(b - b'a') as usize] += 1;
    }

    for right in 0..s.len() {
        window[(s[right] - b'a') as usize] += 1;

        while (right - left + 1) > p_len {
            window[(s[left] - b'a') as usize] -= 1;
            left += 1;
        }

        if (right - left + 1) == p_len && window == target {
            ans.push(left as i32);
        }
    }

    ans
}