news 2026/5/24 9:09:31

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

作者头像

张小明

前端开发工程师

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/5/20 4:45:25

殡葬服务悼词撰写:家属口述内容转化为庄重语音

殡葬服务悼词撰写&#xff1a;家属口述内容转化为庄重语音 在殡仪馆的追思厅里&#xff0c;一段低沉而真挚的悼词缓缓响起——不是由某位亲属颤抖着念出&#xff0c;也不是由主持人机械地播报&#xff0c;而是通过AI技术&#xff0c;将一位逝者子女含泪讲述的回忆&#xff0c;转…

作者头像 李华
网站建设 2026/5/21 15:27:37

乡村信息化普及:农民用方言操控智能灌溉系统

乡村信息化普及&#xff1a;农民用方言操控智能灌溉系统 在四川丘陵地带的一处农田边&#xff0c;老张对着田头的语音终端说了句&#xff1a;“把东头那块地浇一下&#xff0c;水别太大。”不到两秒&#xff0c;喇叭里传出一口熟悉的本地口音&#xff1a;“已启动东部灌溉区&am…

作者头像 李华
网站建设 2026/5/19 1:17:58

揭秘FastAPI跨域预检机制:5分钟掌握OPTIONS请求处理核心技巧

第一章&#xff1a;FastAPI跨域预检机制概述在构建现代Web应用时&#xff0c;前端与后端常部署在不同的域名或端口上&#xff0c;导致浏览器出于安全考虑触发同源策略限制。FastAPI作为高性能的Python Web框架&#xff0c;通过集成CORSMiddleware中间件来处理跨域资源共享&…

作者头像 李华
网站建设 2026/5/19 12:11:22

电竞比赛解说生成:AI辅助打造沉浸式观赛体验

电竞比赛解说生成&#xff1a;AI辅助打造沉浸式观赛体验 在一场关键的《英雄联盟》全球总决赛中&#xff0c;Knight的辛德拉精准释放Q技能&#xff0c;瞬间完成双杀。几乎就在击杀发生的同一帧&#xff0c;观众耳机里传来一声激动的播报&#xff1a;“Knight&#xff01;完美施…

作者头像 李华
网站建设 2026/5/1 9:40:55

HuggingFace镜像网站同步更新VoxCPM-1.5-TTS最新版本

HuggingFace镜像网站同步更新VoxCPM-1.5-TTS最新版本 在语音合成技术加速落地的今天&#xff0c;一个能用几秒钟参考音频就“复刻”出某人声音、还能以接近CD级音质输出中文语音的大模型&#xff0c;正悄然降低AI语音应用的门槛。最近&#xff0c;HuggingFace国内镜像站点同步上…

作者头像 李华
网站建设 2026/5/20 8:26:37

自闭症儿童康复训练:温和语音刺激语言能力发展

自闭症儿童康复训练&#xff1a;温和语音刺激语言能力发展 在儿童发育干预领域&#xff0c;语言能力的迟滞始终是自闭症谱系障碍&#xff08;ASD&#xff09;家庭和康复机构面临的核心挑战之一。许多孩子并非“不愿说”&#xff0c;而是缺乏足够稳定、可预测且情感友好的语言输…

作者头像 李华