滑动窗口详解:解决无重复字符的最长子串问题
滑动窗口详解:解决无重复字符的最长子串问题
在算法面试中,“无重复字符的最长子串”问题是一个经典题目,不仅考察基础数据结构的运用,还能够反映你的逻辑思维能力。而在解决这个问题时,滑动窗口(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)。 技术亮点: 集成第三方身份认证(如 …...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...