news 2026/4/15 15:02:33

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

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
双指针专题(四):像毛毛虫一样伸缩——「长度最小的子数组」

场景想象:

你有一条毛毛虫(窗口),它趴在一个数字数组上。

它的目标是:吃够一定的“营养值”(数组元素之和 $\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”**了吗?

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/4/15 12:38:16

显存不足无法训练大模型?,掌握这7个Python技巧轻松应对

第一章&#xff1a;Python大模型显存占用的核心挑战在深度学习领域&#xff0c;随着模型规模的持续扩大&#xff0c;显存管理成为制约训练与推理效率的关键瓶颈。Python作为主流的开发语言&#xff0c;其生态中的PyTorch、TensorFlow等框架虽提供了高层次的抽象接口&#xff0c…

作者头像 李华
网站建设 2026/4/15 12:36:10

海外华人思乡慰藉:听到家乡话感觉亲人就在身边

海外华人思乡慰藉&#xff1a;听到家乡话感觉亲人就在身边 在温哥华的某个清晨&#xff0c;一位年过七旬的老母亲打开手机&#xff0c;播放一段语音&#xff1a;“阿妈&#xff0c;我今朝煮了你教我的梅菜扣肉&#xff0c;味道好像同你在厨房做的一模一样。”声音一起&#xff…

作者头像 李华
网站建设 2026/4/15 12:43:17

开源社区贡献指南:普通开发者也能参与模型优化

开源社区贡献指南&#xff1a;普通开发者也能参与模型优化 在语音助手、有声书生成和无障碍技术日益普及的今天&#xff0c;高质量文本转语音&#xff08;TTS&#xff09;系统正从实验室走向千家万户。然而&#xff0c;大多数先进TTS模型仍停留在论文或代码仓库中&#xff0c;部…

作者头像 李华
网站建设 2026/4/15 13:48:33

为什么你的PyWebIO文件下载慢如蜗牛?:优化性能的7个关键点

第一章&#xff1a;PyWebIO文件上传下载性能问题概述在基于浏览器的交互式应用开发中&#xff0c;PyWebIO提供了一种轻量级的Python Web界面构建方案。尽管其语法简洁、上手迅速&#xff0c;但在处理大文件上传与下载场景时&#xff0c;常暴露出显著的性能瓶颈。这些问题主要体…

作者头像 李华
网站建设 2026/4/15 14:10:49

ChromeDriver下载地址汇总?不如先了解VoxCPM-1.5-TTS部署依赖

ChromeDriver下载地址汇总&#xff1f;不如先了解VoxCPM-1.5-TTS部署依赖 在AI语音技术飞速发展的今天&#xff0c;越来越多开发者开始尝试将文本转语音&#xff08;TTS&#xff09;能力集成到自己的项目中。然而&#xff0c;当人们还在搜索引擎里反复查找“ChromeDriver 下载地…

作者头像 李华
网站建设 2026/4/15 14:11:22

失眠人群助眠故事:AI生成舒缓语气引导入睡

失眠人群助眠故事&#xff1a;AI生成舒缓语气引导入睡 在深夜的寂静中&#xff0c;一个人辗转反侧&#xff0c;思绪纷乱。手机屏幕亮起&#xff0c;他打开一个网页&#xff0c;输入一段温柔的文字&#xff1a;“你正躺在柔软的草地上&#xff0c;微风轻拂脸颊&#xff0c;远处传…

作者头像 李华