【leetcode C++】滑动窗口

1. LCR 008. 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0 。

题目链接

. - 力扣(LeetCode)

画图 和 文字 分析

先说说有关滑动窗口的知识

滑动窗口特征和步骤:

  1. 无论是出窗口,还是进窗口,都是往一个方向上移动(不会后退)
  2. 步骤:
  • 进窗口
  • 检查
  • 出窗口
  • 更新数据(具体放的位置因题而异)

回到这道题,为什么符合滑动窗口的思想呢?

让 left = 0 , right = 0

通过 right 遍历数组 ,得到区间的所有数之和 sum

sum 与 target 相比

  1. 如果 sum < target

right++(进窗口)

     2. 如果 sum >= target (检查)

记录此时的区间长度 (更新数据)

left++(出窗口), sum -= (left 之前所指向的数),直到 回到第一种情况(里层循环结束条件)

外层循环结束条件(right >= n)

注意:

  1. 记录我们用 count 表示,由于求最小长度,count 的初始化为 INT_MAX , 如果最后没有进入更新数据那一块(整个数组之和 < target),记得判断 count 的值

举例:

输入:target = 7, nums = [2,3,1,2,4,3]

输出:2

 代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
       int sum =0;
       int left = 0;
       int right = 0;
       int count = INT_MAX;
       while(right < nums.size())
       {
          sum += nums[right];
          while(sum >= target)
          {
            if(right - left + 1 < count)
            {
              count = right - left + 1;
            }
            left++;
            sum -= nums[left - 1];
          }
          right++;
       }
       if(count == INT_MAX)
       {
         count = 0;
       }
       return count;
    }
};

2. LCR 016. 无重复字符的最长子串

题目

给定一个字符串 s ,请你找出其中不含有重复字符的 最长连续子字符串 的长度。

题目链接

. - 力扣(LeetCode)

画图 和 文字 分析

步骤:

定义两个指针 , left = 0 , right = 0 , hash数组(存放字符的个数)

  1. 当 hash[right] <= 1

right++(进窗口)

     2. 当 hash[right] > 1(出窗口)

更新数据

left++ ,同时 hash[left - 1]-- ,直到回到第一种情况(里层循环结束条件)

外层结束条件(right >= n)

注意:

  1. 这种方法存在遗漏的情况,跳出整个循环后,一定要最后更新一下(如果碰到整个数组都没有重复元素的情况,不最后检查一下就是错误的)
  2. 如果不想实现注意事项一,那么把更新数据提前到进窗口那一步即可

举例:(题解二的做法)

输入: s = "abcabcbb"

输出: 3

 代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
          int n = 0;
          int hash[128] = {0};
          int left = 0;
          int right = 0;
          while(right < s.size())
          {
            hash[s[right]]++;
            if(hash[s[right]] == 2)
            {
                n = max(n,right - left);
               while(s[left] != s[right])
               {
                  hash[s[left]]--;
                  left++;
               }
                hash[s[left]]--;
               left++;
               right++;
            }
            else
            {
                right++;
            }
          }
          n = max(n,(int)s.size() - left);
          return n;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515353.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何自动申请免费的HTTPS证书?

在购买域名的时候我相信很多人都遇到了对于证书的问题&#xff0c;之前我也是使用阿里云的免费一年的证书&#xff0c;那时候感觉还好&#xff0c;一年更换一次&#xff0c;但是近期阿里云对于证书的过期时间直接砍到了三个月&#xff01;让我难以接受&#xff0c;所以我在想吧…

WPF中动画教程(DoubleAnimation的基本使用)

实现效果 今天以一个交互式小球的例子跟大家分享一下wpf动画中DoubleAnimation的基本使用。该小球会移动到我们鼠标左键或右键点击的地方。 该示例的实现效果如下所示&#xff1a; 页面设计 xaml如下所示&#xff1a; <Window x:Class"AnimationDemo.MainWindow&qu…

Harbor私有镜像仓库搭建

一、介绍 Docker容器应用的开发和运行路不开可靠的镜像管理&#xff0c;虽然Docker官方也提供了公共的镜像仓库&#xff0c;但是从安全和效率等方面考虑&#xff0c;部署我们私有环境的Registry也是非常必要的。 Harbor是由VMware公司开源的企业级的Docker Registry管理项目&a…

面试算法-139-盛最多水的容器

题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&#xff1a;你不能倾斜容器。…

STM32单片机智能电表交流电压电流程序设计(电流 电压互感器TV1005M+TA1005M)

资料下载地址&#xff1a;STM32单片机智能电表交流电压电流程序设计(电流 电压互感器TV1005MTA1005M) 1、摘要 5、基于STM32F103单片机智能电表交流电压电流设计 本设计由STM32单片机核心板电路交流电压电流检测模块电路WIFI模块电路指示灯电路组成。 1、通过电压互感器TV100…

C++模板实参推断

模板实参推断 我们已经看到&#xff0c;对于函数模板&#xff0c;编译器利用调用中的函数实参来确定其模板参数。 从函数实参来确定模板实参的过程被称为模板实参推断。 也就是说&#xff0c;只有函数参数才配有模板实参推断&#xff0c;函数返回类型是不配有的 在模板实参…

DNS搭建

DNS搭建 一、DNS简介 1、概念 DNS&#xff08;Domain Name System&#xff09;是一种分布式的命名系统&#xff0c;用于将域名与其对应的IP地址相互映射。简单来说&#xff0c;DNS充当了互联网上的“电话簿”&#xff0c;帮助用户通过易于记忆的域名查找到相应的网络资源&am…

调用飞书获取用户Id接口成功,但是没有返回相应数据

原因&#xff1a; 该自建应用没有开放相应的数据权限。 解决办法&#xff1a; 在此处配置即可。

Python打包exe文件——pyinstaller模块

Python打包exe文件——pyinstaller模块 目录 Python打包exe文件——pyinstaller模块介绍安装打包文件夹模式打包单文件模式方式SPEC打包(推荐) 介绍 当要在没有python环境的设备上运行python文件时就可以将环境变量全部封装成exe文件发送给对方&#xff0c;此时就可以使用打包…

使用Python实现基本的线性回归模型

线性回归是一种简单而强大的统计学方法&#xff0c;用于预测一个因变量与一个或多个自变量之间的关系。在本文中&#xff0c;我们将使用Python来实现一个基本的线性回归模型&#xff0c;并介绍其原理和实现过程。加粗样式 什么是线性回归&#xff1f; 线性回归是一种用于建立…

upload-labs训练平台

GitHub&#xff1a;GitHub - Tj1ngwe1/upload-labs: 一个帮你总结所有类型的上传漏洞的靶场 把下好的文件夹之间拖入到小皮的WWW目录下就可以之间访问网址使用了 目录 Pass-01(前端JS的绕过) (1)抓包绕过 (2)在前端绕过 Pass-02&#xff08;content-type绕过&#xff09;…

kettle快速入门教程

探索数据的深邃奥秘&#xff0c;引领你踏入数据处理的殿堂&#xff01;Kettle&#xff08;Pentaho Data Integration&#xff09;的神奇魔力&#xff0c;将为你解锁数据世界的无限可能。本人基于公司业务实战整理的50篇精华Kettle系列文章&#xff0c;是你的密钥&#xff0c;让…

【大模型应用篇2】提示词实践-短剧文案

在上节课《【大模型应用篇1】学会对模型念咒语》带大家一起学习了提示词工程&#xff0c;我相信大部分朋友学完之后&#xff0c;还是有懵懂的&#xff0c;这节课带大家实操一下提示词的应用场景&#xff0c;现在短剧的创作很火&#xff0c;好看的短剧内容一定不会差&#xff0c…

java自动化测试-03-05java基础之字符串

1、字符串的定义 String是变量类型&#xff0c;表示字符串类型 name是给这个变量起的名字&#xff0c;这个是可以随意取的&#xff0c;只要不是java的关键字就可以了 表示赋值&#xff0c;右边的的内容表示 变量值&#xff0c;对字符串变量进行 赋值&#xff0c;需要用双引号…

idea建多级目录出现问题,报错找不到xml文件,如何解决?

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…

芯片工程系列(6)Chiplet封装

0 英语缩写 chiplet是一个合成词&#xff0c;由chip和let两个单词组合而成。它的意思是“小芯片”&#xff0c;通常指的是一种集成电路中的小型芯片系统级封装&#xff08;System in a Package&#xff0c;SiP&#xff09;系统级芯片&#xff08;System on a Chip&#xff0c;…

【并发编程】CountDownLatch

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;并发编程 ⛺️稳中求进&#xff0c;晒太阳 CountDownLatch 概念 CountDownLatch可以使一个获多个线程等待其他线程各自执行完毕后再执行。 CountDownLatch 定义了一个计数器&#xff0c;…

4.7 数组的读取和写入,type指令和一些杂项

4.7 数组的读取和写入&#xff0c;type指令和一些杂项 可以通过word ptr将db转为dw&#xff0c;然后按照dw的方式去存储数据 1. 段名也可以把其地址赋给变量 assume cs:codesg,ds:data,ss:stack data segmentdb 12,34dw 12,34db hello world data ends stack segmentdb 10 dup…

YOLOv5改进 | 低照度检测 | 2024最新改进CPA-Enhancer链式思考网络(适用低照度、图像去雾、雨天、雪天)

一、本文介绍 本文给大家带来的2024.3月份最新改进机制,由CPA-Enhancer: Chain-of-Thought Prompted Adaptive Enhancer for Object Detection under Unknown Degradations论文提出的CPA-Enhancer链式思考网络,CPA-Enhancer通过引入链式思考提示机制,实现了对未知退化条件下…

Shell GPT:直接安装使用的chatgpt应用软件

ShellGPT是一款基于预训练生成式Transformer模型&#xff08;如GPT系列&#xff09;构建的智能Shell工具。它将先进的自然语言处理能力集成到Shell环境中&#xff0c;使用户能够使用接近日常对话的语言来操作和控制操作系统。 官网&#xff1a;GitHub - akl7777777/ShellGPT: *…