滑动窗口详解:解决无重复字符的最长子串问题
滑动窗口详解:解决无重复字符的最长子串问题
在算法面试中,“无重复字符的最长子串”问题是一个经典题目,不仅考察基础数据结构的运用,还能够反映你的逻辑思维能力。而在解决这个问题时,滑动窗口(Sliding Window)算法可以说是绝对的明星。本篇文章将带你深入理解滑动窗口的原理,并通过代码和案例一步步解析如何应用它解决该问题。
问题描述
给定一个字符串 s
,请你找出其中不含有重复字符的最长子串的长度。
例如:
- 输入:
s = "abcabcbb"
,输出:3
,因为最长子串是 “abc”。 - 输入:
s = "bbbbb"
,输出:1
,因为最长子串是 “b”。 - 输入:
s = "pwwkew"
,输出:3
,因为最长子串是 “wke”。
乍一看,这个问题可能让人觉得需要两重循环暴力解决。但我们如何优化到线性时间复杂度呢?这时,滑动窗口大显身手。
滑动窗口的原理
滑动窗口是一种双指针技巧,通常用来解决子数组或子串相关问题。它的核心思想是:
- 用两个指针标记窗口的左右边界。
- 动态调整窗口大小以满足问题条件。
- 在移动窗口的过程中记录答案。
滑动窗口的优势在于,它可以避免不必要的重复计算,从而优化时间复杂度。
滑动窗口解法详解
我们来看具体的实现:
# 主函数:寻找无重复字符的最长子串
def length_of_longest_substring(s: str) -> int:# 初始化变量char_set = set() # 用于存储窗口内的字符left = 0 # 左指针max_length = 0 # 记录最大子串长度# 遍历字符串for right in range(len(s)):# 当字符重复时,缩小窗口while s[right] in char_set:print(f"重复字符:{s[right]},移除左侧字符:{s[left]}")char_set.remove(s[left])left += 1# 将当前字符加入窗口char_set.add(s[right])# 更新最大长度current_length = right - left + 1max_length = max(max_length, current_length)print(f"窗口:{s[left:right+1]},当前长度:{current_length}")return max_length
代码详解
-
初始化:
char_set
是一个集合,用来存储当前窗口中的字符。left
是滑动窗口的左边界。max_length
用来记录当前最长的无重复子串长度。
-
遍历字符串:
- 用
right
指针扩展窗口。 - 如果
s[right]
在char_set
中,则表示出现了重复字符,需要通过移动左指针left
来缩小窗口,直到重复字符被移除。
- 用
-
更新答案:
- 每次调整窗口后,计算当前窗口的长度,并更新
max_length
。
- 每次调整窗口后,计算当前窗口的长度,并更新
示例运行
我们以 s = "abcabcbb"
为例,逐步运行代码:
- 初始状态:窗口为空,
left = 0
,max_length = 0
。 - 遍历字符串:
- 右指针移动到 0:窗口为 “a”,
max_length = 1
。 - 右指针移动到 1:窗口为 “ab”,
max_length = 2
。 - 右指针移动到 2:窗口为 “abc”,
max_length = 3
。 - 右指针移动到 3:字符 “a” 重复,移除左侧的 “a”,窗口为 “bca”。
- ……
- 最终输出
max_length = 3
。
- 右指针移动到 0:窗口为 “a”,
时间复杂度分析
- 时间复杂度: 每个字符最多被左指针和右指针访问一次,时间复杂度为
O(n)
。 - 空间复杂度: 需要一个集合存储窗口内的字符,空间复杂度为
O(k)
,其中k
是字符集的大小(对于英文字符,k
最多为 26)。
常见扩展问题
- 找出最长子串本身:
如果不仅要返回长度,还要返回子串本身,可以在代码中记录窗口的起始位置。
def longest_substring(s: str) -> str:char_set = set()left = 0max_length = 0start = 0for right in range(len(s)):while s[right] in char_set:char_set.remove(s[left])left += 1char_set.add(s[right])if right - left + 1 > max_length:max_length = right - left + 1start = leftreturn s[start:start + max_length]
- 滑动窗口在其他场景中的应用:
- 滑动窗口求和问题:固定窗口大小,求最大子数组和。
- 双指针应用于字符串匹配问题,如查找最短覆盖子串。
总结
通过滑动窗口,我们可以优雅地解决“无重复字符的最长子串”问题。这种算法思想不仅高效,还能迁移到很多其他问题中。作为算法学习者,理解并掌握滑动窗口是进阶的必经之路。
如果你对滑动窗口有任何问题,或者想探索更多类似问题的解决方法,欢迎在评论区与我交流!
相关文章:
滑动窗口详解:解决无重复字符的最长子串问题
滑动窗口详解:解决无重复字符的最长子串问题 在算法面试中,“无重复字符的最长子串”问题是一个经典题目,不仅考察基础数据结构的运用,还能够反映你的逻辑思维能力。而在解决这个问题时,滑动窗口(Sliding …...
第05章 11 动量剖面可视化代码一则
在计算流体力学(CFD)中,动量剖面(Momentum Profiles)通常用于描述流体在流动方向上的动量分布。在 VTK 中,可以通过读取速度场数据,并计算和展示动量剖面来可视化呈现速度场信息。 示例代码 以…...

MySQL的复制
一、概述 1.复制解决的问题是让一台服务器的数据与其他服务器保持同步,即主库的数据可以同步到多台备库上,备库也可以配置成另外一台服务器的主库。这种操作一般不会增加主库的开销,主要是启用二进制日志带来的开销。 2.两种复制方式…...

Cpp::IO流(37)
文章目录 前言一、C语言的输入与输出二、什么是流?三、C IO流C标准IO流C文件IO流以写方式打开文件以读方式打开文件 四、stringstream的简单介绍总结 前言 芜湖,要结束喽! 一、C语言的输入与输出 C语言中我们用到的最频繁的输入输出方式就是 …...

基于OpenCV实现的答题卡自动判卷系统
一、图像预处理 🌄 二、查找答题卡轮廓 📏 三、透视变换 🔄 四、判卷与评分 🎯 五、主函数 六、完整代码+测试图像集 总结 🌟 在这篇博客中,我将分享如何使用Python结合OpenCV库开发一个答题卡自动判卷系统。这个系统能够自动从扫描的答题卡中提取信…...

如何将电脑桌面默认的C盘设置到D盘?详细操作步骤!
将电脑桌面默认的C盘设置到D盘的详细操作步骤! 本博文介绍如何将电脑桌面(默认为C盘)设置在D盘下。 首先,在D盘建立文件夹Desktop,完整的路径为D:\Desktop。winR,输入Regedit命令。(或者单击【…...
二十三种设计模式-享元模式
享元模式(Flyweight Pattern)是一种结构型设计模式,旨在通过共享相同对象来减少内存使用,尤其适合在大量重复对象的情况下。 核心概念 享元模式的核心思想是将对象的**可共享部分(内部状态)提取出来进行共…...
算法【有依赖的背包】
有依赖的背包是指多个物品变成一个复合物品(互斥),每件复合物品不要和怎么要多种可能性展开。时间复杂度O(物品个数 * 背包容量),额外空间复杂度O(背包容量)。 下面通过题目加深理解。 题目一 测试链接:[NOIP2006 提…...

A7. Jenkins Pipeline自动化构建过程,可灵活配置多项目、多模块服务实战
服务容器化构建的环境配置构建前需要解决什么下面我们带着问题分析构建的过程:1. 如何解决jenkins执行环境与shell脚本执行环境不一致问题?2. 构建之前动态修改项目的环境变量3. 在通过容器打包时避免不了会产生比较多的不可用的镜像资源,这些资源要是不及时删除掉时会导致服…...

飞牛NAS新增虚拟机功能,如果使用虚拟机网卡直通安装ikuai软路由(如何解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题)
文章目录 📖 介绍 📖🏡 演示环境 🏡📒 飞牛NAS虚拟机安装爱快教程 📒🛠️ 前期准备🌐 网络要求💾 下载爱快镜像🚀 开始安装💻 开启IOMMU直通🌐 配置网络🚨 解决OVS网桥绑定失败以及打开ovs后无法访问飞牛nas等问题➕ 创建虚拟机🎯 安装ikuai💻 进…...
蓝桥杯例题四
每个人都有无限潜能,只要你敢于去追求,你就能超越自己,实现梦想。人生的道路上会有困难和挑战,但这些都是成长的机会。不要被过去的失败所束缚,要相信自己的能力,坚持不懈地努力奋斗。成功需要付出汗水和努…...

八股——Java基础(四)
目录 一、泛型 1. Java中的泛型是什么 ? 2. 使用泛型的好处是什么? 3. Java泛型的原理是什么 ? 什么是类型擦除 ? 4.什么是泛型中的限定通配符和非限定通配符 ? 5. List和List 之间有什么区别 ? 6. 可以把List传递给一个接受List参数的方法吗? 7. Arra…...

CVE-2023-38831 漏洞复现:win10 压缩包挂马攻击剖析
目录 前言 漏洞介绍 漏洞原理 产生条件 影响范围 防御措施 复现步骤 环境准备 具体操作 前言 在网络安全这片没有硝烟的战场上,新型漏洞如同隐匿的暗箭,时刻威胁着我们的数字生活。其中,CVE - 2023 - 38831 这个关联 Win10 压缩包挂…...

【自然语言处理(NLP)】深度循环神经网络(Deep Recurrent Neural Network,DRNN)原理和实现
文章目录 介绍深度循环神经网络(DRNN)原理和实现结构特点工作原理符号含义公式含义 应用领域优势与挑战DRNN 代码实现 个人主页:道友老李 欢迎加入社区:道友老李的学习社区 介绍 **自然语言处理(Natural Language Pr…...
Linux 命令之技巧(Tips for Linux Commands)
Linux 命令之技巧 简介 Linux 是一种免费使用和自由传播的类Unix操作系统,其内核由林纳斯本纳第克特托瓦兹(Linus Benedict Torvalds)于1991年10月5日首次发布。Linux继承了Unix以网络为核心的设计思想,是一个性能稳定的多用户…...

【文星索引】搜索引擎项目测试报告
目录 一、项目背景二、 项目功能2.1 数据收集与索引2.2 API搜索功能2.3 用户体验与界面设计2.4 性能优化与维护 三、测试报告3.1 功能测试3.2 界面测试3.3 性能测试3.4 兼容性测试3.5 自动化测试 四、测试总结4.1 功能测试方面4.2 性能测试方面4.3 用户界面测试方面 一、项目背…...

低代码系统-产品架构案例介绍、轻流(九)
轻流低代码产品定位为零代码产品,试图通过搭建来降低企业成本,提升业务上线效率。 依旧是从下至上,从左至右的顺序 名词概述运维层底层系统运维层,例如上线、部署等基础服务体系内置的系统能力,发消息、组织和权限是必…...

二叉树(补充)
二叉树 1.二叉树的基本特性2.堆2.1.堆的基本概念2.2.堆的实现2.2.1.基本结构2.2.2.堆的初始化 2.2.3.堆的销毁2.2.4.堆的插入2.2.5.取出堆顶的数据2.2.6.堆的删除2.2.7.堆的判空2.2.8.堆的数据个数2.2.9.交换2.2.10.打印堆数据2.2.11.堆的创建2.2.12.堆排序 1.二叉树的基本特性…...
(DM)达梦数据库基本操作(持续更新)
1、连接达梦数据库 ./disql 用户明/"密码"IP端口或者域名 2、进入某个模式(数据库,因达梦数据库没有库的概念,只有模式,可以将模式等同于库) set schema 库名; 3、查表结构; SELECT COLUMN_NAM…...
CRM 微服务
文章目录 项目地址一、项目地址 教程作者:教程地址:代码仓库地址:所用到的框架和插件:dbt airflow一、 用户与认证服务 主要功能: 用户注册、登录、注销。 认证(OAuth、JWT 等)。 权限和角色管理(RBAC/ABAC)。 单点登录(SSO)。 技术亮点: 集成第三方身份认证(如 …...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...