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/16 10:21:12

表单上传总失败?,深度剖析PyWebIO文件上传常见坑及避坑方案

第一章&#xff1a;表单上传失败的常见现象与背景在现代Web应用开发中&#xff0c;文件上传是用户与系统交互的重要功能之一&#xff0c;广泛应用于头像设置、文档提交和媒体资源管理等场景。然而&#xff0c;表单上传失败是开发者频繁遇到的问题&#xff0c;其表现形式多样&am…

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

X射线检测技术:多领域关键应用与性能发展趋势解析

X射线检测技术&#xff0c;是一种成熟的无损检测的手段&#xff0c;它在工业领域发挥着不可替代的作用&#xff0c;它在食品领域发挥着不可替代的作用&#xff0c;它在安检等多个关键领域发挥着不可替代的作用&#xff0c;其核心原理在于利用X射线穿透物质&#xff0c;由于物质…

作者头像 李华
网站建设 2026/4/16 10:18:46

AI排名优化技术解析:原理、服务商与应用场景

于当下数字化营销的环境里头&#xff0c;AI排名优化已然成了企业用以提升在线可见度以及获取精准流量的关键技术办法&#xff0c;此技术主要借由算法去剖析搜索引擎跟内容平台的排名机制&#xff0c;联合语义理解呀、用户意图识别还有实时数据反馈&#xff0c;针对特定关键词或…

作者头像 李华
网站建设 2026/4/16 10:17:25

导师推荐9个AI论文写作软件,专科生轻松搞定毕业论文!

导师推荐9个AI论文写作软件&#xff0c;专科生轻松搞定毕业论文&#xff01; AI 工具如何助力论文写作&#xff0c;让专科生轻松应对毕业挑战 在当前教育环境中&#xff0c;越来越多的专科生面临毕业论文的撰写压力。面对复杂的格式要求、繁重的文献查阅以及反复的修改过程&…

作者头像 李华
网站建设 2026/4/16 10:18:34

2025空间智能技术大爆发

2025年超图技术&#xff0c;空间智能软件技术的进化与深耕 这篇文章是关于2025年空间智能软件技术的进化与深耕的技术合集&#xff0c;重点介绍了SuperMap GIS 2025在多个领域的技术突破和应用创新。以下是文章的主要内容&#xff1a; 地理空间AI 技术突破&#xff1a;2…

作者头像 李华
网站建设 2026/4/16 10:22:19

MyBatisPlus是否可用于存储VoxCPM-1.5-TTS的语音日志数据?

MyBatisPlus 是否可用于存储 VoxCPM-1.5-TTS 的语音日志数据&#xff1f; 在构建 AI 驱动的语音服务时&#xff0c;一个常被忽视但至关重要的环节是——如何高效、可靠地管理生成过程中的各类数据。比如&#xff0c;当用户通过网页输入一段文字&#xff0c;系统调用 VoxCPM-1.5…

作者头像 李华