双指针专题(四)：像毛毛虫一样伸缩——「长度最小的子数组」

场景想象：

你有一条毛毛虫（窗口），它趴在一个数字数组上。

它的目标是：吃够一定的“营养值”（数组元素之和 $\ge$ target）。

• 策略：

  1. 进食（右指针向右伸）：为了吃饱，它必须把头往前伸，把新的数字吞进来。

  2. 消化（左指针向右缩）：一旦吃饱了（和 $\ge$ target），它觉得自己太胖了，为了保持“身材苗条”（长度最小），它会尝试把尾巴缩回来（吐出左边的数字），看看是不是还能保持饱腹状态。

这就是滑动窗口的核心逻辑：进窗口 -> 判断 -> 出窗口。

力扣 209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

题目分析：

• 输入：正整数数组nums，正整数target。

• 目标：找到一个连续子数组，使得其和 $\ge$target。

• 输出：满足条件的最小长度。如果没有，返回 0。

例子：target = 7, nums = [2, 3, 1, 2, 4, 3]

1. [2, 3, 1]和是 6，不够。

2. [2, 3, 1, 2]和是 8，够了！长度 4。

   • 尝试缩尾巴：去掉 2，[3, 1, 2]和是 6，不够了。

3. 继续伸头...[3, 1, 2, 4]和是 10，够了！

   • 缩尾巴：去掉 3，[1, 2, 4]和是 7，够了！长度 3。

   • 再缩尾巴：去掉 1，[2, 4]和是 6，不够。

4. 继续伸头...[2, 4, 3]和是 9，够了！

   • 缩尾巴：去掉 2，[4, 3]和是 7，够了！长度 2。

   • 再缩尾巴：去掉 4，[3]和是 3，不够。

最终答案：2。

核心思维：$O(N)$ 的魔法

如果用暴力解法，我们需要两层循环（枚举所有起点和终点），复杂度是 $O(N^2)$。

而滑动窗口只需要两个指针配合，right 指针主动走，left 指针被动走。

每个元素最多被“进窗口”一次，被“出窗口”一次。所以复杂度是 $O(N)$。

代码实现 (JavaScript)

这是滑动窗口最标准的模板，背下来能应付 80% 的同类题。

JavaScript

/** * @param {number} target * @param {number[]} nums * @return {number} */ var minSubArrayLen = function(target, nums) { let left = 0; // 窗口左边界 let right = 0; // 窗口右边界 let sum = 0; // 窗口内元素的和 let result = Infinity; // 记录最小长度，初始化为无穷大 // 1. 右指针主动向右滑动，扩大窗口 while (right < nums.length) { // --- 进窗口 --- sum += nums[right]; // 2. 当窗口内的和满足条件时，尝试收缩左边界 // 注意：这里用 while，因为可能需要连续缩好几次 // 比如 [100, 1, 1, 1], target=100。读到100时直接满足，后面可能还要继续缩。 while (sum >= target) { // 更新最小长度 let currentLen = right - left + 1; result = Math.min(result, currentLen); // --- 出窗口 --- sum -= nums[left]; left++; // 左边界向右收缩 } // 继续寻找下一个 right++; } // 如果 result 还是 Infinity，说明整个数组加起来都没 target 大 return result === Infinity ? 0 : result; };

深度辨析：为什么是 While 而不是 If？

在收缩窗口的时候：

JavaScript

while (sum >= target) { ... }

很多初学者会写成 if。

如果是 if，意味着你每加进来一个新数字，左边最多只缩一步。

但在本题中，假设 nums = [1, 1, 1, 1, 100], target = 100。

• 当right走到100时，sum变成了 104。

• 此时满足条件。如果你只缩一步（去掉第一个 1），sum变成 103，还是满足条件，其实应该继续缩！

• 我们需要把左边的1, 1, 1, 1全部缩掉，只留下[100]，才能得到最优解。

• 所以必须用while，直到不能缩为止。

总结

这道题是不定长滑动窗口的开山之作。

• 特征：求“最长/最短/满足条件”的连续子数组。

• 模板：

  • 外层循环移动right（扩张）。

  • 内层循环移动left（收缩，寻找最优解）。

下一题预告：无重复字符的最长子串

接下来这道题LC 3. 无重复字符的最长子串，是 LeetCode全站排名第一的题目（无论按热度还是按面试频率）。

• 它也是滑动窗口，但稍微变了一点点：

• 这一次，窗口收缩的条件不是“和大于等于 target”，而是**“窗口里出现了重复字符”**。

• 比如abcabcbb，当你遇到第二个a时，左指针该怎么动？

准备好挑战这道**算法界的“Hello World”**了吗？