news 2026/5/1 7:30:25

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

作者头像

张小明

前端开发工程师

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/20 0:54:20

Python 3D图形开发必知(视角控制技术全公开)

第一章&#xff1a;Python 3D视角控制概述在科学计算与数据可视化领域&#xff0c;Python 凭借其丰富的库生态系统&#xff0c;成为实现三维场景构建与视角操控的首选语言。通过 Matplotlib、Plotly、Mayavi 和 PyVista 等工具&#xff0c;开发者能够灵活定义观察角度、旋转中心…

作者头像 李华
网站建设 2026/4/29 9:19:49

Python树状数据序列化实战精要(资深架构师20年经验总结)

第一章&#xff1a;Python树状数据序列化概述在现代软件开发中&#xff0c;树状结构被广泛应用于表示层级关系&#xff0c;如文件系统、组织架构和XML/HTML文档。当需要将这些结构持久化或通过网络传输时&#xff0c;序列化成为关键步骤。Python提供了多种机制来实现树状数据的…

作者头像 李华
网站建设 2026/4/17 18:51:38

使用Jupyter Notebook调试VoxCPM-1.5-TTS-WEB-UI输出结果

使用Jupyter Notebook调试VoxCPM-1.5-TTS-WEB-UI输出结果 在语音合成技术飞速发展的今天&#xff0c;一个看似简单的“文字转语音”功能背后&#xff0c;往往隐藏着复杂的深度学习模型与工程架构。开发者常常面临这样的困境&#xff1a;Web界面操作便捷&#xff0c;但缺乏对内…

作者头像 李华
网站建设 2026/5/1 7:28:51

家族族谱语音记录:后代子孙聆听祖先奋斗历程

家族记忆的温度&#xff1a;当AI让祖辈的声音再次响起 在一场家族聚会上&#xff0c;一位年轻人用手机播放了一段录音&#xff1a;“祖父生于1930年&#xff0c;曾参与抗美援朝……”声音苍劲有力&#xff0c;语调熟悉得让人眼眶发热——这并不是某段尘封的老磁带&#xff0c;而…

作者头像 李华
网站建设 2026/4/25 13:14:08

刚刚开源!谷歌AI测试平台正在颠覆我们的工作方式

12月21日凌晨&#xff0c;Google突然宣布将其企业级AI测试平台TensorQA正式开源。这个原本每年收费50万美元的测试解决方案&#xff0c;现在任何测试团队都能免费接入。消息公布2小时内&#xff0c;GitHub星标数突破3000&#xff0c;HackerNews热度TOP 3。 技术拆解&#xff1a…

作者头像 李华
网站建设 2026/4/27 23:40:01

将VoxCPM-1.5-TTS嵌入企业客服系统的可行性研究

将VoxCPM-1.5-TTS嵌入企业客服系统的可行性研究 在当前智能服务快速演进的背景下&#xff0c;客户对语音交互体验的期待已远超“能听清、能回应”的基本要求。越来越多的企业开始追求更具亲和力、个性化甚至“人格化”的语音服务——这背后&#xff0c;正是高质量文本转语音&am…

作者头像 李华