C++ 优先算法 —— 长度最小的子数组(滑动窗口)

devtools/2024/11/26 11:18:00/

目录

题目:长度最小的子数组 

1. 题目解析

2. 算法原理

Ⅰ. 暴力枚举

Ⅱ. 滑动窗口(同向双指针)

滑动窗口正确性

3. 代码实现

Ⅰ. 暴力枚举(会超时)

Ⅱ. 滑动窗口(同向双指针)


题目:长度最小的子数组 

1. 题目解析

题目截图:

 这里需要注意一些题目的细节问题,如下:

上面 [4,3] 这个子数组符合 ≥target 的条件且是最短的长度为 2,所以,结果输出为 2

若是数组中的其中一个值作为子数组就能满足 ≥target 的,最小长度的子数组长度必定是1。

若数组中所有的值相加都是 < target ,那么不存在符合条件的子数组(整个数组也算是数组的子数组),就返回0。

2. 算法原理

这道题有两种解法:

  • 暴力枚举
  • 滑动窗口(同向双指针)

Ⅰ. 暴力枚举

暴力枚举:这里就是枚举出所有的子数组之和,判断它是否满足要求。

这里还可以优化一下,优化成O(N²):

题目中,已经强调是一个正整数数组,数组里面的元素全都是 >0 的,在做加法的时候,加的数越多,和就越大(单调性)。

这样就可以省去再从前到后遍历一遍子数组了,这里还可以再优化一下: 

也就是sum符合结果时,再向后枚举都符合结果(正整数数组),但是len是递增的,不符合要求,后面不需考虑。

接着让 left 往后移动一位,让 right 回退到 left 的位置 ,继续枚举。

Ⅱ. 滑动窗口(同向双指针)

在暴力枚举最后的优化情况,还可以观察到一个优化的地方:

此时 right 就可以不动,没有必要再让 right 回退到 left 的位置遍历再计算这一小段的子数组的和了,只需要更新 sum 即可(让 sum 减去 left 上一次指向的元素)。

这样就可以用双指针来解决了,也就是:利用单调性,使用同向双指针(两个指针移动方向一致)来优化。

同向双指针也称作滑动窗口。

什么时候用滑动窗口呢?

也就是利用单调性的时候。当发现利用暴力解法的时候,两个指针都可以做到不回退,都向同一个方向移动的时候,此时就可以用滑动窗口(本质就是同向双指针)。

怎么用滑动窗口?

  1. 先初始化 left 和 right (左端点,右端点)                                                                                                left = 0 , right = 0 (用它俩分别标记窗口的左右区间)
  2. 进窗口
  3. 判断: 根据判断是否出窗口

(其中2、3步是循环的) 

进窗口,在这里就是right所指向的元素进入窗口,进入窗口之后,sum就要更新 。

 接着再让right往后移动即可,再接着判断:

再重复操作

 right再向后移动1位时:

此时,就可以更新以下结果了,这里结果就是len(子数组长度)。 

 更新完结果之后,再出窗口,这里就是让left向右移动一位,出窗口时候还需要把sum更新一下:

 出完窗口之后继续判断:

这时,又到了进窗口之后判断的操作了: 

注意:出完窗口时候还要继续判断, 因为可能依旧是大于等于target,若满足,还需要更新结果再出窗口:

此时,又观察到,sum<target,不满足要求,继续进窗口:

判断,又满足了要求,再接着出窗口(重复上面的操作):

判断,又得出sum>target,继续出窗口:

判断,不满足要求 ,继续让right向后移动(进窗口):

但此时可以观察到,没有下一个元素了,这时让right指向的下一个元素就已经越界了,这时窗口就结束了。此时这个 len 就是最终结果。

所以,大方向分为三步:1. 进窗口  。2. 判断。3. 出窗口。

这里更新结果需要看题目要求:有的需要进窗口时更新,有的需要出窗口时更新,有的会在出窗口之后再更新。

滑动窗口正确性

虽然并没有把所有的情况都给枚举出来,但是已经直到接下来的情况是没有必要的行为,因此是利用单调性,规避了很多没有必要的枚举行为。 

这里时间复杂度:根据实际情况是每一步操作仅仅会让 right 向右移动 1 位或 left 向右移动 1 位,直到 right 移动到最后的位置。这里最差的情况下,也就是 n+n  ->  2n 次,所以就是 O(N)。 

3. 代码实现

题目链接:长度最小的子数组

Ⅰ. 暴力枚举(会超时)

//代码实现
//时间复杂度:O(N²)
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int len = INT_MAX;for(int left = 0; left < n; left++){int sum = 0;for (int right = left; right < n; right++){sum += nums[right];if(sum >= target){len = min(len,right-left+1);break;}}}return len==INT_MAX?0:len;}
};

提交记录:(会超时)

Ⅱ. 滑动窗口(同向双指针)

//代码实现
//注意这里虽然有两个循环,但是要根据实际情况
//时间复杂度:O(N)
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size(), sum=0,len=INT_MAX;//sum标记维护窗口的和,len标记最终结果for(int left = 0, right = 0; right < n; right++){sum += nums[right];      //进窗口while(sum >= target)     //判断是否要出窗口,用while循环确保连续出窗口的情况{len = min(len, right - left + 1);    //更新结果sum -= nums[left++];                 //出窗口}}return len == INT_MAX ? 0 : len;}
};

提交记录:

制作不易,若有不足之处或出问题的地方,请各位大佬多多指教 ,感谢大家的阅读支持!!!    


http://www.ppmy.cn/devtools/137106.html

相关文章

【GPT】睡觉时,大脑在做什么

睡觉时&#xff0c;大脑并不是完全“关闭”的&#xff0c;而是处于高度活跃的状态&#xff0c;进行许多重要的功能。以下是大脑在不同睡眠阶段的主要活动&#xff1a; 1. 修复与恢复 神经元修复&#xff1a;大脑细胞会修复白天受到的损伤&#xff0c;同时清除代谢废物&#xf…

【ArcGISPro】使用AI提取要素-土地分类(sentinel2)

Sentinel2数据处理 【ArcGISPro】Sentinel-2数据处理-CSDN博客 土地覆盖类型分类 处理结果

51单片机快速入门之中断的应用 2024/11/23 串口中断

51单片机快速入门之中断的应用 基本函数: void T0(void) interrupt 1 using 1 { 这里放入中断后需要做的操作 } void T0(void)&#xff1a; 这是一个函数声明&#xff0c;表明函数 T0 不接受任何参数&#xff0c;并且不返回任何值。 interrupt 1&#xff1a; 这是关键字和参…

安全近期汇总

奇安信在 2024 年世界互联网大会相关展示与分析展望 一、奇安信展示产品 QAX - GPT 安全机器人 采用 Agent 思路&#xff0c;划分为四个核心专家角色&#xff1a; 全能型安全专家。网络威胁研判专家。终端威胁研判专家。主机威胁研判专家。四大拳头产品 AISOC、天眼、天擎和椒…

软件工程——面向对象概述

&#xff08;1&#xff09;对象 在应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象&#xff0c;它既可以是具体的物理实体的抽象&#xff0c;也可以是人为的概念&#xff0c;或者是任何有明确边界和意义的东西。例如&#xff0c;一名职工、一家公司、一个…

Python编程整理汇总(基础汇总版)

1. 基础语法 1.1 变量与数据类型 整数&#xff1a;a 10 浮点数&#xff1a;b 3.14 字符串&#xff1a;c "Hello, World!" 布尔值&#xff1a;d True 列表&#xff1a;e [1, 2, 3, 4, 5] 元组&#xff1a;f (1, 2, 3) 字典&#xff1a;g {"name&qu…

如何通过 Java 实现 HTTPS 匿名 POST 提交

在开发过程中,我们经常会遇到需要通过 HTTPS 协议向服务器发送 POST 请求的情况。特别是在处理自签名证书或测试环境中,我们可能需要忽略 SSL 证书验证。本文将详细介绍如何使用 Java 实现这一功能,并提供优化后的代码示例。 背景 在实际开发中,我们可能会遇到以下几种情…

【Linux】常用系统工作命令

常用系统工作命令 1.echo2.date3.timedatectl4.wget5.ps6.pstree7.top8.nice9.pidof10.kill11.killall 1.echo echo 命令的作用是向用户显示一行文本。它可以用于各种情况&#xff0c;比如在脚本中输出提示信息、打印变量值、生成日志文件等等。 输出字符串。 echo "He…