长度最小的子数组:右扩到「达标」,再尽力缩左
与无重复字符的最长子串同为变长窗口,但目标反过来——求最短。给一串正整数和一个 target,找和 ≥ target 的最短连续子数组。思路:右指针
R 不断纳入新数把窗口和撑大;一旦窗口和达到 target,就立刻反过来缩左——在「仍达标」的前提下尽量移除左边的数,把窗口压到最短,每缩一步都记录长度。L、R 仍是只增不减,各扫一遍 →
。
1 · 和「求最长」的镜像关系
无重复最长子串是「窗口违反约束时被迫缩左,合法时记录最长」;这页是「窗口达标后主动缩左,每次缩之前记录最短」。一个在「不得不缩」时记录、一个在「还能缩」时记录——这就是变长窗口求最长 / 最短两类题的分界。本题依赖全正数(加数只增、减数只降,窗口和随 L/R 单调),左缩判断才如此简单;若含负数,需要换成前缀和 + 单调队列的做法。
**回到话题主线:**无论定长还是变长,滑动窗口的共同内核都是「窗口随下标单向移动 + 增量维护窗内信息」,把嵌套两层的 / 压成一遍扫描的 。它正是 双指针里「同向双指针」流派最常见的落地形态;工程中的应用场景见应用实例。