滑动窗口(2)_无重复字符的最长字串
个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创滑动窗口(2)_无重复字符的最长字串
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌
目录
1. 题目链接:
2. 题目描述 :
3. 解法 :
解法一(暴力枚举) :
算法思路 :
具体步骤 :
代码展示 :
结果分析 :
解法二(滑动窗口) :
算法思路 :
图解流程:
代码展示:
结果分析:
滑动窗口的正确性:
时间复杂度分析:
1. 题目链接:
OJ链接:无重复字符的最长字串
2. 题目描述 :
给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke"是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
3. 解法 :
解法一(暴力枚举) :
算法思路 :
枚举[从每一个位置]开始往后,无重复字符的字串可以到达什么位置.找出其中长度最大的即可.
在往后寻找无重复字串能到达的位置时,可以利用[哈希标]统计出字符出现的频次,来判断什么时候字串出现了重复元素.
具体步骤 :
- 定义两个指针i,j遍历数组
- j++,向后移动寻找与i重复的数
- j找到与i相同的数,更新字串长度.
- 然后i++,j = i,重新重新寻找下一个数的最长无重复字串

代码展示 :
class Solution {
public:int lengthOfLongestSubstring(string s) {int len = 0, n = s.size();for(int i = 0; i < n; i++){int hash[128] = {0};for(int j = i; j < n; j++){hash[s[j]]++;if(hash[s[j]] > 1) break;len = max(len, j - i + 1); }}return len;}
};

结果分析 :
!!!!!!!!!!!!!!!!!!!!!!
居然过了?这已经是第二个算法题能直接用暴力通过了
还是老样子,分析一下题目的数据范围:
0 <= s.length <= 5 * 104字符串的长度区间范围:[0, 5*10^4],没超过10^5就给了暴力枚举的机会
我们暴力枚举的时间复杂度为O(N^2),这样数据级别大于10^9小于10^10是有机会通过的.
如果这道题更狠的话,直接把数据修改为10^5之内的字符,那我们的暴力枚举直接退役了
解法二(滑动窗口) :
算法思路 :
我们发现暴力算法真的很无脑,比如:

研究的对象依旧是一段连续的区间,因此继续使用[滑动窗口]思想来优化.
让滑动窗口满足: 窗口内所有元素都是不重复的.
做法: 右端元素right进入窗口的时候,哈希表统计这个字符的频次:
如果这个字符出现的频次超过1,说明窗口内有重复元素,那么就从左侧开始划出窗口.直到right这个元素的频次变为1,然后更新结果.
如果没有超过1,说明当前窗口没有重复元素,可以直接更新结果
基本思路:
- left = 0, right = 0;
- 进窗口 ------> 让字符进入哈希表
- 循环判断
- 窗口内出现重复字符(提前结束循环)
- 出窗口 ------- > 从哈希表中删除该字符
- 更新结果
图解流程:





代码展示:
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0};int left = 0, right = 0, n = s.size();int ret = 0;while(right < n){hash[s[right]]++;while(hash[s[right]] > 1) hash[s[left++]]--;ret = max(ret, right - left + 1);right++;}return ret;}
};

结果分析:
滑动窗口的正确性:
我们这里使用滑动窗口解决了暴力枚举的重复遍历
时间复杂度分析:
时间复杂度: O(N)
空间复杂度: 我们开了一个hash数组,但只有128个空间,也就是常数级别,可以忽略不记,所以时间复杂度为O(1)
相关文章:
滑动窗口(2)_无重复字符的最长字串
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 滑动窗口(2)_无重复字符的最长字串 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌 目…...
c语言 —— 结构变量
1.结构变量的定义 类型和变量是不同的概念,只能对变量进行赋值、存取或运算操作,而不能对一个类型进行这些操作。因此在声明了结构类型后,还需要定义结构变量,以便在程序中引用它。结构变量和其他变量一样,必须先定义后使用,定义方法有以下3种: (1)先定义结构类型,再定…...
一个py脚本,提供处理 GET 请求返回网站数据,处理 POST 请求接收并打印数据。支持跨域访问。
from flask import Flask, jsonify, request from flask_cors import CORSapp Flask(__name__)# 允许跨域请求 CORS(app)app.route(/getapi/getadate/test2, methods[GET]) def get_data():response_data {"sites": [{"name": "菜鸟教程", &qu…...
【Elasticsearch系列六】系统命令API
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
c++概念
C语言设计期末考试知识点 1. 基础语法 变量和数据类型: int, float, double, char, bool 等基本数据类型。常量:const 关键字。变量的作用域:局部变量、全局变量。 输入输出: cin 和 cout:标准输入输出流。格式化输出…...
Makefile 学习笔记(一)gcc编译过程
环境准备 .linux 系统(虚拟机) VS code linux 编译过程 预处理: 把.h .c 展开形成一个文件.宏定义直接替换 头文件 库文件 .i 汇编: .i 生成一个汇编代码文件 .S 编译: .S 生成一个 .o .obj 链接: .o 链接 .exe .elf gcc c语言 g c语言 gcc的使用 …...
mybatis的基本使用与配置
注释很详细,直接上代码 项目结构 源码 UserMapper package com.amoorzheyu.mapper;import com.amoorzheyu.pojo.User; import org.apache.ibatis.annotations.Mapper; import org.apache.ibatis.annotations.Select;import java.util.List;Mapper //在运行时生成代…...
2022高教社杯全国大学生数学建模竞赛C题 问题三问题四 Python代码
目录 问题33.1 对附件表单 3 中未知类别玻璃文物的化学成分进行分析,鉴别其所属类型3.2 对分类结果的敏感性进行分析 问题44.1 针对不同类别的玻璃文物样品,分析其化学成分之间的关联关系绘图散点图相关系数图 问题3 3.1 对附件表单 3 中未知类别玻璃文物…...
易于理解和实现的Python代码示例
一些示例代码段,但请注意,由于无法直接执行或访问特定环境,将提供一些通用的、易于理解和实现的Python代码示例。这些示例旨在展示编程的不同方面,从基础到稍微复杂一点的概念。 示例1:简单的Python函数 def greet(n…...
Visual Studio 2019/2022 IntelliCode(AI辅助IntelliSense)功能介绍
IntelliCode 不知在多久以前,我装上了Visual Studio 2019,写代码时,就注意到了下面这样的东西:带五角星的提示。 这个带五角星的提示功能叫做IntelliCode。 我们知道Visual Studio 有个强大的功能叫做Intellisense(智能感知)&am…...
mac安装swoole过程
1.很重要的是得根据自己环境的php版本来选择swoole版本!否则都是做无用功。 Swoole 文档 2.通常pecl install swoole是安装最新版本的,当然安装的方式很多种,这里选择编译安装,因为可以选择不同的swoole版本进行安装,…...
代码随想录算法训练营第三十二天 | 509. 斐波那契数,70. 爬楼梯,746. 使用最小花费爬楼梯
第三十二天打卡,动态规范第一天!今天比较简单,主要理解dp的概念 509.斐波那契数列 题目链接 解题过程 状态转移方程 dp[i] dp[i - 1] dp[i - 2]; 动态规划 class Solution { public:int fib(int n) {if (n < 2) return n;int dp[n …...
Oracle发送邮件功能:配置自动化发信指南?
Oracle发送邮件服务设置方法?怎么用Oracle数据库发信? Oracle数据库作为企业级应用的核心,其内置的发送邮件功能为企业提供了强大的自动化工具。AokSend将详细介绍如何配置Oracle发送邮件功能,以实现自动化发信,从而提…...
探索 InternLM 模型能力边界
Bad Case 1. 模型服务来源compassarea输入我刚才问了什么问题模型AInternLM2.5-20B-Chat (上海AILab书生浦语)模型BQwen2-72B-Instruct (阿里通义千问)模型A输出对不起,由于我无法访问之前的交互历史记录,我无法回答您刚才问的具体问题是什么。不过&am…...
Python 数学建模——Pearson/Spearman 相关系数
文章目录 前言原理关于 p p p 值Pearson 相关系数代码实例Spearman 相关系数代码实例求相关系数求相关系数矩阵 前言 相关系数尝尝用来衡量两个数值变量之间是否存在某种关系。我们常说的“正相关”“负相关”就是这种相关关系。而相关系数的绝对值大小体现了相关关系的强弱。…...
QUIC的loss detection学习
PTO backoff backoff 补偿 /ˈbkɒf/PTO backoff 是QUIC(Quick UDP Internet Connections)协议中的一种机制,用于处理探测超时(Probe Timeout, PTO)重传策略 它逐步增加探测超时的等待时间,以避免网络拥塞…...
【QT】使用QOpenGLWidget后,窗口全屏之后右键菜单出不来的问题
问题 QMainWindow全屏之后,发现右键菜单出不来了,后来排查到问题是和窗口中使用了QOpenGLWidget控件有关系。 解决方案 在QMainWindow构造函数末尾,添加这句话(作用是给窗口周围增加1像素线,实现伪全屏)…...
MySQL 8.0授权语法变更及解决方案
MySQL 8.0授权语法变更及解决方案 授权语法变更:MySQL 8.0更改了授权语法,无法直接在授权语句中使用IDENTIFIED BY来创建用户并设置密码。需要先创建用户,再单独授权。 创建用户并授权: 使用CREATE USER语句创…...
2024 VMpro 虚拟机中如何给Ubuntu Linux操作系统配置联网
现在这是一个联网的状态 可以在商店里面下载东西 也能ping成功 打开虚拟网络编辑器 放管理员权限 进行设置的更改 选择DNS设置 按提示修改即可 注意的是首选的DNS服务器必须是114.114.114.114 原因 这边刚刚去查了一下 114.114.114.114 是国内的IP地址 8.8.8.8 是国外的I…...
详解Diffusion扩散模型:理论、架构与实现
本文深入探讨了Diffusion扩散模型的概念、架构设计与算法实现,详细解析了模型的前向与逆向过程、编码器与解码器的设计、网络结构与训练过程,结合PyTorch代码示例,提供全面的技术指导。 关注TechLead,复旦AI博士,分享A…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解
文章目录 一、开启慢查询日志,定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...
