不定长滑动窗口是双指针技术中最核心、最实用的算法模式之一，广泛用于求解连续子数组/子串的最值问题。
一、核心概念
滑动窗口用两个指针left和right表示一个连续区间[left, right]。指针只向右移动，通过动态调整窗口大小，避免暴力枚举的\(O(n^2)\)复杂度。
| 类型 | 窗口大小 | 典型问题 |
|---|---|---|
| 定长窗口 | 固定 k |
子数组平均数、固定长度最大和 |
| 不定长窗口 | 动态变化 | 最长/最短满足某条件的连续子区间 |
二、什么时候用（前提条件）
使用不定长滑动窗口必须满足以下条件：
- 连续性：求的是子数组/子串（不能跳元素）
- 单调性：
- 扩大窗口（
right++）可能使条件从满足变为不满足，或从不满足变为满足。 - 缩小窗口（
left++）的作用与扩大窗口相反。
- 扩大窗口（
- 可快速维护：窗口状态（和、频次、极值等）能在\(O(1)\)更新。
❌ 不适用场景：子序列问题、条件无单调性（如“窗口内乘积为质数”）、需要全局排序
三、代码模板
不定长窗口通常分为两类：求最长和求最短。模板结构几乎一致，仅更新答案时机不同。
🔹 模板 A：求最长满足条件的连续子数组/子串
public int longestWindow(int[] nums /*, 其他参数 */) {int left = 0;int maxLen = 0;// 【初始化】窗口状态变量（如 sum=0, int[] freq, HashMap, valid 计数等）for (int right = 0; right < nums.length; right++) {// 1️⃣ 扩大窗口：将 right 元素加入窗口// addToWindow(nums[right]);// 2️⃣ 条件不满足时，收缩左边界while (!isValidWindow()) {// removeFromWindow(nums[left]);left++;}// 3️⃣ 此时窗口一定合法，更新最大长度maxLen = Math.max(maxLen, right - left + 1);}return maxLen;
}
🔹 模板 B：求最短满足条件的连续子数组/子串
public int shortestWindow(int[] nums /*, target 等参数 */) {int left = 0;int minLen = Integer.MAX_VALUE;// 【初始化】窗口状态变量for (int right = 0; right < nums.length; right++) {// 1️⃣ 扩大窗口// addToWindow(nums[right]);// 2️⃣ 条件满足时，尝试收缩找更短的合法窗口while (isValidWindow()) {minLen = Math.min(minLen, right - left + 1);// removeFromWindow(nums[left]);left++;}}// 未找到合法窗口时返回 0 或题目要求的默认值return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
Java 性能建议：字符频次统计优先用
int[128]或int[26]，比HashMap<Character, Integer>快 3~5 倍且无装箱开销。
避坑指南
| 坑点 | 正确写法 |
|---|---|
minLen 初始值用 0 |
必须用 Integer.MAX_VALUE，最后判断返回 0 |
while 写成 if |
条件可能连续触发，必须用 while |
left 越界检查 |
滑动窗口中 left 永远不会超过 right + 1，一般无需额外判断 |
字符串频繁 charAt |
可提前 char[] arr = s.toCharArray(); 提升速度 |
| 大数求和溢出 | 窗口和可能超 int 时，状态变量改用 long |
leetcode题单
【算法题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）