当前位置：首页 > news >正文

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

news 2026/5/12 11:16:34

场景想象：

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

它的目标是：吃够一定的“营养值”（数组元素之和 $\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]

[2, 3, 1]和是 6，不够。
[2, 3, 1, 2]和是 8，够了！长度 4。
- 尝试缩尾巴：去掉 2，[3, 1, 2]和是 6，不够了。
继续伸头...[3, 1, 2, 4]和是 10，够了！
- 缩尾巴：去掉 3，[1, 2, 4]和是 7，够了！长度 3。
- 再缩尾巴：去掉 1，[2, 4]和是 6，不够。
继续伸头...[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; };