前端进阶之旅前端进阶之旅
  • 基础篇HTML/CSS/JS 打底
  • 进阶篇原理与工程化
  • 高频篇面试最常问的那批
  • 精选篇按模块收敛的总结
  • 手写篇常考代码手写实现
  • 面经篇真实面试问题复盘
  • AI 篇NEWAI 时代的前端考点
  • 历年面经NEW按年份追踪真实考点
  • 每日一题每天一道,攒手感
  • 专项自测100 题快速查漏
  • 小程序题库小程序专项刷题
  • 算法题库NEW在线编码即时判题
  • 知识卡片NEW碎片时间过考点
  • 面试题大全常见问题解析
  • AI 答疑NEW随时提问,即时解析
  • AI 模拟面试NEW模拟真实面试 + 报告
  • AI 定制路线NEW按你的简历现排
  • AI 知识地图NEW串起全站知识点
  • 原理篇React / Vue 源码拆解
  • HTTP从报文一路讲到 HTTPS
  • 浏览器渲染、事件循环、进程
  • 计算机基础Linux、网络、操作系统
  • 设计模式23 种模式怎么用
  • Node学习指南从环境搭建到服务端
  • NPM工作流script、依赖与发布
  • Docker容器化部署上手
  • Canvas图形与动画实战
  • 前端系统进阶学习大型项目工程化
  • 前端综合文章长期沉淀的实践文
  • 思维导图知识点全景图
  • 学习路线按图索骥不跑偏
  • AI 热点NEWAI 每日动态
  • 公众号动态公众号历史文章
  • 博客动态站长的技术博客
  • 开发者导航常用工具与文档站
  • 基础篇HTML/CSS/JS 打底
  • 进阶篇原理与工程化
  • 高频篇面试最常问的那批
  • 精选篇按模块收敛的总结
  • 手写篇常考代码手写实现
  • 面经篇真实面试问题复盘
  • AI 篇NEWAI 时代的前端考点
  • 历年面经NEW按年份追踪真实考点
  • 每日一题每天一道,攒手感
  • 专项自测100 题快速查漏
  • 小程序题库小程序专项刷题
  • 算法题库NEW在线编码即时判题
  • 知识卡片NEW碎片时间过考点
  • 面试题大全常见问题解析
  • AI 答疑NEW随时提问,即时解析
  • AI 模拟面试NEW模拟真实面试 + 报告
  • AI 定制路线NEW按你的简历现排
  • AI 知识地图NEW串起全站知识点
  • 原理篇React / Vue 源码拆解
  • HTTP从报文一路讲到 HTTPS
  • 浏览器渲染、事件循环、进程
  • 计算机基础Linux、网络、操作系统
  • 设计模式23 种模式怎么用
  • Node学习指南从环境搭建到服务端
  • NPM工作流script、依赖与发布
  • Docker容器化部署上手
  • Canvas图形与动画实战
  • 前端系统进阶学习大型项目工程化
  • 前端综合文章长期沉淀的实践文
  • 思维导图知识点全景图
  • 学习路线按图索骥不跑偏
  • AI 热点NEWAI 每日动态
  • 公众号动态公众号历史文章
  • 博客动态站长的技术博客
  • 开发者导航常用工具与文档站
首页程序员面试题库可变滑动窗口 最短子数组
算法算法数组与双指针

可变滑动窗口求最短满足条件的子数组时,收缩窗口的条件如何判断?

窗口满足目标条件的那一轮立即收缩左指针;每向右移动一次左指针前都更新最短长度,直到条件被破坏或左指针越过右端。

前端进阶之旅 · 一题精讲更新于 2026.09.05
算法#数组与双指针
先看核心答案读代码示例
理解线索

满足即缩,逐点判断

  1. 触发时机当前窗口达到目标条件时启动左移
  2. 收缩停止条件不再满足或左指针越过右端点
  3. 单调保障扩展使条件更容易满足才可单调

若数组含负数或性质不具备单调性,本方法可能失效。

核心回答

先记住这个答案

当右指针扩展使窗口第一次满足条件时启动收缩:记录当前窗口长度;然后右移左指针,每移一步若窗口仍满足条件就更新最短长度并继续,直到条件不再满足或窗口为空。这样收缩依赖单调性,左指针只向右不回退,因此不会漏掉更优解,整体复杂度是 O(n)。

  • 满足条件后立即尝试收缩左指针
  • 收缩过程中逐步更新最短窗口
  • 左指针单调右移才能保证不错过最优

收缩时的核心判断规则

可变滑动窗口求最短解时,右指针不断外扩使窗口从“不满足”变为“满足”。一旦条件成立,当前窗口就是右端为 i 时的一个候选解,也是可能继续缩短的起点。此时应让左指针向右逐个试探。每次移动前先记录当前满足条件的窗口长度,然后减去原左端值并右移左指针;移动后若窗口仍未失去条件,说明还能更短,继续重复记录与移动。只有当条件破裂后,才停止本轮收缩并继续外扩右指针。

收缩不影响最优性的根本原因在于性质的单调方向。典型的正整数求和问题里,窗口总和随扩展右端只增不减,因此右端越靠右,满足“和≥target”所需的最小左端只会向右或不动,绝不会回退。所以每一个被右移过的左端点都不会再与更远的右端构成更优答案,双指针可以线性推进;收缩中每一步都更新,即使最佳窗口恰好出现在收缩到一半时,也能被记录下来。

正整数数组最短和 ≥ 目标值的长度JavaScript
const minSubArrayLen = (target, nums) => {
  let left = 0;
  let sum = 0;
  let best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return Number.isFinite(best) ? best : 0;
};

console.log('target=7, [2,3,1,2,4,3]:', minSubArrayLen(7, [2,3,1,2,4,3]));
console.log('target=7, []:', minSubArrayLen(7, []));
console.log('target=2, [1,3,1]:', minSubArrayLen(2, [1,3,1]));
console.log('target=5, [1,2,2]:', minSubArrayLen(5, [1,2,2]));
查看输出与解释
target=7, [2,3,1,2,4,3]: 2
target=7, []: 0
target=2, [1,3,1]: 1
target=5, [1,2,2]: 3

时间复杂度 O(n),空间 O(1)。每个元素最多进入窗口一次、离开窗口一次。空数组或无法达到目标时返回 0。

网络请求日志中定位最短高峰窗口

假设某服务每分钟请求计数为 [7,1,2,3,5,4],运维想找到总请求数至少达到 10 的最短连续分钟段。右指针从 0 起累加,到索引 2 时总和为 10,第一次满足条件,于是立即收缩。先记录长度 3(索引 0 到 2),左移移除 7 后总和变 3,不满足,收缩停止;随后右指针继续扩大窗口。最终在索引 4 到 5 之间收缩出长度 2 的窗口吗?实际模拟得到最优是索引 2 到 4 的长度 3,算法输出 3。

这个场景说明每删除一个左边界前都要记录当前长度,不能等一次性删到不能再删才记录。因为删掉 7 后窗口不满足了,但如果之前没有记录长度 3,就可能漏掉以索引 0–2 为右端点终点的候选解。虽然它不是最优,但无法提前知道。更关键的是,当后续右指针到索引 3 时,我们又需要重新评估收缩,直到找到最短为 3 的解。

什么情况下不能这样收缩

本文方法的前提是窗口状态关于扩展具有单调性:右端外扩会使“满足目标”从假变真,但不会从真变假。正整数数组和 ≥ target 满足这点,覆盖目标字符类问题中增加字符不会让已覆盖集合消失,也满足。但若数组中存在负数,总和可能因扩展右端而下降,原本满足的窗口可能变成不满足,左指针对应的最小可行位置不再单调,继续使用这种收缩会错失解。

面对负数,需要换用前缀和加单调队列,或采用二分长度检查等代价更高的算法;全零元素通常不破坏单调性,但会延长收缩过程的时间。另一个边界是当数组本来就无法满足条件时,需要显式返回 0。示例中的空数组或所有正数之和仍小于 target 都应落到这个分支,避免把 Infinity 当结果返回。

回答前,多想一步

容易答错的地方

收缩时只记录最终状态
有人会在 while 中直接跳过被删元素,等 left 停在第一个不满足的位置后才记录一次。但最短窗口可能出现在删除一步或几步后、还未破坏条件时;丢失中间记录会直接漏解。正确做法是在每次删除前都记录当前满足条件的长度。
条件破坏后继续收缩
有人为了让窗口更短,会在窗口已经不满足后还继续右移 left,认为之后右端加入元素时可能再达标。这不会得到合法的候选解,还会把左指针推得过远;即使后续重新满足,可能需要回退左指针,但单调假设下回退是多余的,继续推更会错过正确起点。应该在 while 条件为假时立刻停止本轮收缩。
试着用自己的话回答

面试官还会怎么问?

为什么收缩完成的左指针在后续扩展中不需要回退?

因为条件具有单调性:右端外扩只会让窗口状态更容易满足,因此满足条件所需的最左下标也只能向右移动,不会向左。所以每个左指针一旦被移出窗口,就不会再参与到更优的窗口组合里,可以放心继续向右推进。

最小覆盖子串问题的收缩条件与和值问题有何不同?

和的对比用数值 sum 比较简单;覆盖子串需要记录目标字符的剩余计数,并统计当前还缺多少种字符。当“缺失种类数”为 0 时,就相当于条件满足,可以收缩左指针,每次移动后若移除的字符导致某些字符不够,则重新进入不满足状态。判断方法换成哈希表,收缩框架一致。

数组中有 0 或负数时分别怎么处理?

0 不会破坏单调非减,可继续用本方法,但可能在收缩时总和不变,循环多执行几次。负数会让扩展右端可能减少总和,单调性不成立,不适合双指针收缩;应改用前缀和相关结构,或配合其他算法。

从一道题,走向一组知识

把知识连起来

图算法

为什么 BFS 能在无权图中求出单源最短路径?

继续了解 BFS 无权图 最短路,补充本题涉及的 算法 相关知识。

动态规划

动态规划和贪心算法的决策方式有什么本质区别,为什么贪心在有些最优化问题上失效?

继续了解 动态规划 贪心算法 区别,补充本题涉及的 算法 相关知识。

参考资料

  • Algorithms for Competitive Programming¶

示例用于理解所注明的运行环境与边界;延伸学习可结合原文中的更多案例。

本题目录
  1. 先记住这个答案
  2. 收缩时的核心判断规则
  3. 网络请求日志中定位最短高峰窗口
  4. 什么情况下不能这样收缩
  5. 容易答错的地方
  6. 面试官还会怎么问
  7. 把知识连起来
读懂,再试着讲出来

先看核心答案,再读代码。最后展开追问,检查自己有没有遗漏边界。

试着回答追问
浏览全部面试题理解原理,也关注真实的使用场景。回到顶部 ↑