滑动窗口算法详解

滑动窗口是一种在数组或字符串上移动的「窗口」技术，用于高效解决子数组/子串问题。

一、什么是滑动窗口

想象一个在数组上滑动的窗口，窗口内的元素就是我们要处理的数据。

字符串："abcabcbb"

窗口移动过程：
"abc" → 扩展遇到重复的 'a'
"bca" → 收缩后重新扩展
"cab" → 继续移动
"abc" → 继续移动
"bc"  → 继续移动
"c"   → 继续移动
"b"   → 结束

最长不重复子串长度：3 ("abc")

核心思想：

• 用两个指针表示窗口的左右边界
• 右指针不断向右扩展窗口
• 当遇到重复元素时，移动左指针收缩窗口
• 窗口内的数据满足某种条件

二、实战例题

2.1 无重复字符的最长子串

题目： 找出不含有重复字符的最长子串长度

输入："abcabcbb"
输出：3
解释：无重复字符的最长子串是 "abc"

核心思路： 用哈希表记录窗口内的字符，右指针扩展，左指针收缩

import java.util.HashSet;

public class LongestSubstring {

  public static int lengthOfLongestSubstring(String s) {
    HashSet<Character> window = new HashSet<>();
    int max = 0;
    int n = s.length();

    for (int i = 0; i < n; i++) {
      // 左指针每次移动都要清空窗口
      window.clear();

      // 用右指针扩展窗口
      int rightIndex = i;
      while (rightIndex < n && !window.contains(s.charAt(rightIndex))) {
        window.add(s.charAt(rightIndex));
        rightIndex++;
      }

      // 记录当前窗口长度
      max = Math.max(max, rightIndex - i);
    }

    return max;
  }

  public static void main(String[] args) {
    String s = "abcabcbb";
    // 输出: 3
  }
}

理解要点：

• 左指针决定窗口的起始位置
• 右指针决定窗口的结束位置
• 窗口内的字符不能重复，遇到重复就停止扩展

2.2 找到字符串中所有字母异位词

题目： 在字符串 s 中找到所有 p 的字母异位词的起始位置

输入：s = "cbaebabacd", p = "abc"
输出：[0, 6]
解释：s[0..2]="cba"，s[6..8]="bac"

核心思路： 固定大小的滑动窗口 + 字符频次对比

import java.util.*;

public class FindAnagrams {

  public static List<Integer> findAnagrams(String s, String p) {
    if (s.isEmpty() || p.isEmpty()) return new ArrayList<>();

    List<Integer> ans = new ArrayList<>();
    int windowSize = p.length();

    // 统计 p 的字符频次
    int[] pCount = new int[26];
    for (char c : p.toCharArray()) {
      pCount[c - 'a']++;
    }

    // 遍历所有可能的窗口
    for (int i = 0; i < s.length() - windowSize + 1; i++) {
      int[] window = new int[26];

      // 统计窗口内字符频次
      for (int j = i; j < i + windowSize; j++) {
        window[s.charAt(j) - 'a']++;
      }

      // 对比两个频次数组
      if (Arrays.equals(window, pCount)) {
        ans.add(i);
      }
    }

    return ans;
  }

  public static void main(String[] args) {
    String s = "cbaebabacd";
    String p = "abc";
    // 输出: [0, 6]
  }
}

理解要点：

• 窗口大小固定为 p 的长度
• 用数组统计字符出现次数
• 频次相同就是异位词

2.3 和为 K 的子数组

题目： 统计和为 K 的连续子数组个数

输入：[1, 2, 3], K = 3
输出：2
解释：[1,2] 和 [3]

核心思路： 前缀和 + 哈希表记录前缀和出现次数

import java.util.HashMap;

public class SubarraySum {

  public static int subarraySum(int[] nums, int k) {
    int ans = 0, sum = 0;
    HashMap<Integer, Integer> prefixMap = new HashMap<>();

    // 初始化：前缀和为 0 出现 1 次
    prefixMap.put(0, 1);

    for (int i = 0; i < nums.length; i++) {
      // 计算当前前缀和
      sum += nums[i];

      // 查找是否存在前缀和 = sum - k
      // 如果存在，说明中间的子数组和为 k
      if (prefixMap.containsKey(sum - k)) {
        ans += prefixMap.get(sum - k);
      }

      // 记录当前前缀和
      prefixMap.put(sum, prefixMap.getOrDefault(sum, 0) + 1);
    }

    return ans;
  }

  public static void main(String[] args) {
    int[] nums = {1, 2, 3};
    int k = 3;
    // 输出: 2
  }
}

理解要点：

• 前缀和 = 从开头到当前位置的所有元素之和
• 前缀和[j] - 前缀和[i] = k 等价于「从 i+1 到 j 的子数组和为 k」
• 用哈希表记录每个前缀和出现的次数

三、总结

题目	窗口特点	核心技巧
无重复字符最长子串	可变大小	用集合判断重复
字母异位词	固定大小	对比字符频次
和为 K 的子数组	可变大小	前缀和 + 哈希表

滑动窗口使用场景：

• 寻找满足条件的子数组/子串
• 需要在 O(n) 时间内解决
• 条件可以「窗口滑动时动态维护」

模板总结：

// 滑动窗口通用模板
int left = 0, right = 0;
while (right < n) {
  // 1. 将 right 位置的元素加入窗口
  add(window, nums[right]);
  right++;

  // 2. 当窗口不满足条件时，收缩左边界
  while (window 不满足条件) {
    remove(window, nums[left]);
    left++;
  }

  // 3. 更新答案
  update(answer);
}